MIT Open Access Articles: Recent submissions

Now showing items 22-24 of 55022

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

    • Rounding Large Independent Sets on Expanders 

      Bafna, Mitali; Hsieh, Jun-Ting; Kothari, Pravesh K. (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has its second eigenvalue bounded away from ...

    • Universal SNARGs for NP from Proofs of Correctness 

      Jin, Zhengzhong; Kalai, Yael Tauman; Lombardi, Alex; Mathialagan, Surya (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We give new constructions of succinct non-interactive arguments (SNARGs) for NP in the settings of both non-adaptive and adaptive soundness. Our construction of non-adaptive SNARG is universal assuming the security of a ...