MIT Open Access Articles: Recent submissions

Now showing items 43-45 of 55118

    • Classical Commitments to Quantum States 

      Gunn, Sam; Tauman Kalai, Yael; Natarajan, Anand; Vill?nyi, ?gi (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We define the notion of a classical commitment scheme to quantum states, which allows a quantum prover to compute a classical commitment to a quantum state, and later open each qubit of the state in either the standard or ...

    • Symmetric Perceptrons, Number Partitioning and Lattices 

      Vafa, Neekon; Vaikuntanathan, Vinod (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      The symmetric binary perceptron (SBPκ) problem with parameter κ : ℝ≥1 → [0,1] is an average-case search problem defined as follows: given a random Gaussian matrix A ∼ N(0,1)n × m as input where m ≥ n, output a vector x ∈ ...

    • DNF Learning via Locally Mixing Random Walks 

      Alman, Josh; Nadimpalli, Shivam; Patel, Shyamal; Servedio, Rocco A. (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We give two results on PAC learning DNF formulas using membership queries in the challenging “distribution-free” learning framework, where learning algorithms must succeed for an arbitrary and unknown distribution over ...