MIT Open Access Articles

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