MIT Open Access Articles: Recent submissions

Now showing items 7-9 of 55096

    • Weak Recovery, Hypothesis Testing, and Mutual Information in Stochastic Block Models and Planted Factor Graphs 

      Mossel, Elchanan; Sly, Allan; Sohn, Youngtak (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      The stochastic block model is a canonical model of communities in random graphs. It was introduced in the social sciences and statistics as a model of communities, and in theoretical computer science as an average case ...

    • Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations 

      Bangachev, Kiril; Bresler, Guy; Tiegel, Stefan; Vaikuntanathan, Vinod (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We present a polynomial-time reduction from solving noisy linear equations over in dimension Θ(klogn/(logk,logq,loglogn)) with a uniformly random coefficient matrix to noisy linear equations over in dimension n where each ...

    • Stochastic Matching via In-n-Out Local Computation Algorithms 

      Azarmehr, Amir; Behnezhad, Soheil; Ghafari, Alma; Rubinfeld, Ronitt (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      Consider the following stochastic matching problem. We are given a known graph G=(V, E). An unknown subgraph Gp = (V, Ep) is realized where Ep includes every edge of E independently with some probability p ∈ (0, 1]. The ...