MIT Open Access Articles: Recent submissions

Now showing items 31-33 of 55096

    • Simulating Time with Square-Root Space 

      Williams, R. Ryan (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We show that for all functions t(n) ≥ n, every multitape Turing machine running in time t can be simulated in space only O(√t logt). This is a substantial improvement over Hopcroft, Paul, and Valiant’s simulation of time ...

    • Model Stealing for Any Low-Rank Language Model 

      Liu, Allen; Moitra, Ankur (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      Model stealing, where a learner tries to recover an unknown model via carefully chosen queries, is a critical problem in machine learning, as it threatens the security of proprietary models and the privacy of data they are ...

    • Maximum Circuit Lower Bounds for Exponential-Time Arthur Merlin 

      Chen, Lijie; Li, Jiatu; Liang, Jingxun (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We show that the complexity class of exponential-time Arthur Merlin with sub-exponential advice (AMEXP/2nε) requires circuit complexity at least 2n/n. Previously, the best known such near-maximum lower bounds were for ...