Volume 17 (2021)
Vol 17, Article 1 (pp 1-30)
[CCC19 Spec Issue]
Limits on the Universal Method for Matrix Multiplication
by Josh Alman
Limits on the Universal Method for Matrix Multiplication
by Josh Alman
Vol 17, Article 2 (pp 1-32)
[CCC19 Spec Issue]
Barriers for Fast Matrix Multiplication from Irreversibility
by Matthias Christandl, Péter Vrana, and Jeroen Zuiddam
Barriers for Fast Matrix Multiplication from Irreversibility
by Matthias Christandl, Péter Vrana, and Jeroen Zuiddam
Vol 17, Article 3 (pp 1-4)
[APRX-RND19 Spec Issue]
Special Issue: APPROX-RANDOM 2019: Guest Editors' Foreword
by Noga Ron-Zewi, Ivona Bezáková, and László Végh
Special Issue: APPROX-RANDOM 2019: Guest Editors' Foreword
by Noga Ron-Zewi, Ivona Bezáková, and László Végh
Vol 17, Article 4 (pp 1-35)
[APRX-RND19 Spec Issue]
Deterministic Approximation of Random Walks in Small Space
by Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil Vadhan
Deterministic Approximation of Random Walks in Small Space
by Jack Murtagh, Omer Reingold, Aaron Sidford, and Salil Vadhan
Vol 17, Article 5 (pp 1-27)
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
by Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
by Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi
Vol 17, Article 6 (pp 1-57)
Almost Polynomial Hardness of Node-Disjoint Paths in Grids
by Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat
Almost Polynomial Hardness of Node-Disjoint Paths in Grids
by Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat
Vol 17, Article 7 (pp 1-46)
[APRX-RND19 Spec Issue]
The Large-Error Approximate Degree of AC$^0$
by Mark Bun and Justin Thaler
The Large-Error Approximate Degree of AC$^0$
by Mark Bun and Justin Thaler
Vol 17, Article 8 (pp 1-28)
The Layer Complexity of Arthur-Merlin-like Communication
by Dmitry Gavinsky
The Layer Complexity of Arthur-Merlin-like Communication
by Dmitry Gavinsky
Vol 17, Article 9 (pp 1-30)
[CCC19 Spec Issue]
Sherali--Adams Strikes Back
by Ryan O'Donnell and Tselil Schramm
Sherali--Adams Strikes Back
by Ryan O'Donnell and Tselil Schramm
Vol 17, Article 10 (pp 1-88)
[CCC16 Spec Issue]
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
by Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
by Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson
Vol 17, Article 11 (pp 1-38)
[CCC19 Spec Issue]
Hardness Magnification Near State-of-the-Art Lower Bounds
by Igor C. Oliveira, Ján Pich, and Rahul Santhanam
Hardness Magnification Near State-of-the-Art Lower Bounds
by Igor C. Oliveira, Ján Pich, and Rahul Santhanam