MIT Open Access Articles: Recent submissions

Now showing items 16-18 of 55022

    • Constant Degree Networks for Almost-Everywhere Reliable Transmission 

      Bafna, Mitali; Minzer, Dor (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      In the almost-everywhere reliable message transmission problem, introduced by [Dwork, Pippenger, Peleg, Upfal’86], the goal is to design a sparse communication network G that supports efficient, fault-tolerant protocols ...

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