MIT Open Access Articles: Recent submissions

Now showing items 19-21 of 55022

    • Sandwiching Random Geometric Graphs and Erdos-Renyi with Applications: Sharp Thresholds, Robust Testing, and Enumeration 

      Bangachev, Kiril; Bresler, Guy (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      The distribution RGG(n,Sd−1,p) is formed by sampling independent vectors {Vi}i = 1n uniformly on Sd−1 and placing an edge between pairs of vertices i and j for which ⟨ Vi,Vj⟩ ≥ τdp, where τdp is such that the expected ...

    • Sample-Optimal Private Regression in Polynomial Time 

      Anderson, Prashanti; Bakshi, Ainesh; Majid, Mahbod; Tiegel, Stefan (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We consider the task of privately obtaining prediction error guarantees in ordinary least-squares regression problems with Gaussian covariates (with unknown covariance structure). We provide the first sample-optimal ...

    • Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence 

      Nogler, Jakob; Polak, Adam; Saha, Barna; Vassilevska Williams, Virginia; Xu, Yinzhan; e.a. (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      The tree edit distance (TED) between two rooted ordered trees with n nodes labeled from an alphabet Σ is the minimum cost of transforming one tree into the other by a sequence of valid operations consisting of insertions, ...