- 2022
- Xin Li, Shachar Lovett, Jiapeng Zhang:
Sunflowers and Robust Sunflowers from Randomness Extractors. Theory Comput. 18: 1-18 (2022) - Per Austrin, Petteri Kaski, Kaie Kubjas:
Tensor Network Complexity of Multilinear Maps. Theory Comput. 18: 1-54 (2022) - Amey Bhangale, Subhash Khot:
UG-hardness to NP-hardness by Losing Half. Theory Comput. 18: 1-28 (2022) - Vladimir Braverman, Robert Krauthgamer, Lin F. Yang:
Universal Streaming of Subset Norms. Theory Comput. 18: 1-32 (2022) - Chandra Chekuri, Tanmay Inamdar:
Algorithms for Intersection Graphs for t-Intervals and t-Pseudodisks. Theory Comput. 18: 1-19 (2022) - Zongchen Chen, Santosh S. Vempala:
Optimal Convergence Rate of Hamiltonian Monte Carlo for Strongly Logconcave Distributions. Theory Comput. 18: 1-18 (2022) - Kuan Cheng, William M. Hoza:
Hitting Sets Give Two-Sided Derandomization of Small Space. Theory Comput. 18: 1-32 (2022) - Christian Coester, James R. Lee:
Pure Entropic Regularization for Metrical Task Systems. Theory Comput. 18: 1-24 (2022) - Irit Dinur, Prahladh Harsha, Tali Kaufman, Noga Ron-Zewi:
From Local to Robust Testing via Agreement Testing. Theory Comput. 18: 1-25 (2022) - Andrew Drucker:
Guest Editor's Foreword to the RANDOM 2018 Special Issue. Theory Comput. 18: 1-3 (2022) - Zeev Dvir, Avishay Tal:
Guest Editors' Foreword to the CCC 2020 Special Issue. Theory Comput. 18: 1-4 (2022) - Alon Eden, Uriel Feige, Michal Feldman:
Max-Min Greedy Matching. Theory Comput. 18: 1-33 (2022) - Lukas Fleischer:
The Cayley Semigroup Membership Problem. Theory Comput. 18: 1-18 (2022) - Alexander Golovnev, Ishay Haviv:
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications. Theory Comput. 18: 1-22 (2022) - Kaave Hosseini, Hamed Hatami, Shachar Lovett:
Sign-Rank vs. Discrepancy. Theory Comput. 18: 1-22 (2022) - Stacey Jeffery:
Span Programs and Quantum Space Complexity. Theory Comput. 18: 1-49 (2022) - Alexander Kozachinskiy, Vladimir V. Podolskii:
Multiparty Karchmer-Wigderson Games and Threshold Circuits. Theory Comput. 18: 1-33 (2022) - Maya Leshkowitz:
Round Complexity Versus Randomness Complexity in Interactive Proofs. Theory Comput. 18: 1-65 (2022) - Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan:
Near-Optimal NP-Hardness of Approximating Max k-CSPR. Theory Comput. 18: 1-29 (2022) - Kent Quanrud:
Fast and Deterministic Approximations for k-Cut. Theory Comput. 18: 1-24 (2022) - Rocco A. Servedio, Li-Yang Tan:
Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas. Theory Comput. 18: 1-46 (2022) - Emanuele Viola:
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines. Theory Comput. 18: 1-12 (2022) - Xinyu Wu:
A Stochastic Calculus Approach to the Oracle Separation of BQP and PH. Theory Comput. 18: 1-11 (2022) - 2021
- Amir Abboud, Robert Krauthgamer, Ohad Trabelsi:
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs. Theory Comput. 17: 1-27 (2021) - Josh Alman:
Limits on the Universal Method for Matrix Multiplication. Theory Comput. 17: 1-30 (2021) - Mark Bun, Justin Thaler:
The Large-Error Approximate Degree of AC0. Theory Comput. 17: 1-46 (2021) - Matthias Christandl, Péter Vrana, Jeroen Zuiddam:
Barriers for Fast Matrix Multiplication from Irreversibility. Theory Comput. 17: 1-32 (2021) - Julia Chuzhoy, David Hong Kyun Kim, Rachit Nimavat:
Almost Polynomial Hardness of Node-Disjoint Paths in Grids. Theory Comput. 17: 1-57 (2021) - Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson:
Proof Complexity Lower Bounds from Algebraic Circuit Complexity. Theory Comput. 17: 1-88 (2021) - Dmitry Gavinsky:
The Layer Complexity of Arthur-Merlin-like Communication. Theory Comput. 17: 1-28 (2021)