MIT Open Access Articles: Recent submissions

Now showing items 4-6 of 55096

    • QMA vs QCMA and Pseudorandomness 

      Liu, Jiahui; Mutreja, Saachi; Yuen, Henry (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We study a longstanding question of Aaronson and Kuperberg on whether there exists a classical oracle separating QMA from QCMA. Settling this question in either direction would yield insight into the power of quantum proofs ...

    • Semantics of Integrating and Differentiating Singularities 

      Michel, Jesse; Lee, Wonyeol; Yang, Hongseok (ACM, 2025-06-13)
      A singular function is a partial function such that at one or more points, the left and/or right limit diverge (e.g., the function 1/x). Since programming languages typically support division, programs may denote singular ...

    • SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More 

      Diakonikolas, Ilias; Hopkins, Samuel B.; Pensia, Ankit; Tiegel, Stefan (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We study sparse singular value certificates for random rectangular matrices. If M is a d × n matrix with independent Gaussian entries, we give a new family of polynomial-time algorithms which can certify upper bounds on ...