MIT Open Access Articles: Recent submissions

Now showing items 22-24 of 55096

    • 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 ...

    • Near Optimal Constant Inapproximability under ETH for Fundamental Problems in Parameterized Complexity 

      Bafna, Mitali; Karthik C. S.; Minzer, Dor (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We prove that under the Exponential Time Hypothesis (ETH), for every ε > 0, there exists a constant C > 0 such that no algorithm running in time nk / logC k can determine whether a given 2-CSP instance with k variables, ...