MIT Open Access Articles: Recent submissions

Now showing items 106-108 of 55108

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

    • The Structure of Catalytic Space: Capturing Randomness and Time via Compression 

      Cook, James; Li, Jiatu; Mertz, Ian; Pyne, Edward (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      In the catalytic logspace (CL) model of (Buhrman et. al. STOC 2013), we are given a small work tape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly ...