MIT Open Access Articles: Recent submissions

Now showing items 103-105 of 55108

    • Quasi-Linear Size PCPs with Small Soundness from HDX 

      Bafna, Mitali; Minzer, Dor; Vyas, Nikhil; Yun, Zhiwei (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We construct 2-query, quasi-linear size probabilistically checkable proofs (PCPs) with arbitrarily small constant soundness, improving upon Dinur’s 2-query quasi-linear size PCPs with soundness 1 − Ω(1). As an immediate ...

    • Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time 

      Eden, Talya; Levi, Reut; Ron, Dana; Rubinfeld, Ronitt (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      Counting small subgraphs, referred to as motifs, in large graphs is a fundamental task in graph analysis, extensively studied across various contexts and computational models. In the sublinear-time regime, the relaxed ...

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