MIT Open Access Articles: Recent submissions

Now showing items 1-3 of 55095

    • Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games 

      Daskalakis, Constantinos; Farina, Gabriele; Fishelson, Maxwell; Pipis, Charilaos; Schneider, Jon (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We propose efficient no-regret learning dynamics and ellipsoid-based methods for computing linear correlated equilibria—a relaxation of correlated equilibria and a strengthening of coarse correlated equilibria—in general ...

    • When Connectivity Is Hard, Random Walks Are Easy with Non-determinism 

      Doron, Dean; Pyne, Edward; Tell, Roei; Williams, R. Ryan (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      Two fundamental problems on directed graphs are to decide s-t connectivity, and to estimate the behavior of random walks. Currently, there is no known algorithm for s-t connectivity running in polynomial time and no(1) ...

    • QMA vs QCMA and Pseudorandomness 

      Liu, Jiahui; Mutreja, Saachi; Yuen, Henry (ACM|Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025-06-15)
      We study a longstanding question of Aaronson and Kuperberg on whether there exists a classical oracle separating QMA from QCMA. Settling this question in either direction would yield insight into the power of quantum proofs ...