Articles under category:
Complexity
Complexity
|
ToC Library Graduate Surveys 10 (2025) 166 pages
Introduction to Geometric Complexity Theory by Markus Bläser and Christian Ikenmeyer |
|
Vol 21, Article 8 (pp 1-38)
Seed-Protecting Extractors by Gil Cohen, Dean Doron, and Shahar Samocha |
|
Vol 21, Article 6 (pp 1-29)
Polynomial Calculus Space and Resolution Width by Nicola Galesi, Leszek A. Kołodziejczyk, and Neil Thapen |
|
Vol 21, Article 4 (pp 1-48)
Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds by Yuval Filmus, Massimo Lauria, Mladen Mikša, Jakob Nordström, and Marc Vinyals |
|
Vol 20, Article 5 (pp 1-22)
On the Elementary Construction of High-Dimensional Expanders by Kaufman and Oppenheim by Prahladh Harsha and Ramprasad Saptharishi |
|
Vol 20, Article 4 (pp 1-13)
[Boolean Spec Issue]
Influential Coalitions for Boolean Functions I: Constructions by Jean Bourgain, Jeff Kahn, and Gil Kalai |
|
Vol 20, Article 3 (pp 1-87)
Verifier-on-a-Leash: New Schemes for Verifiable Delegated Quantum Computation, with Quasilinear Resources by Andrea Coladangelo, Alex B. Grilo, Stacey Jeffery, and Thomas Vidick |
|
Vol 20, Article 2 (pp 1-19)
New Distinguishers for Negation-Limited Weak Pseudorandom Functions by Zhihuai Chen, Siyao Guo, Qian Li, Chengyu Lin, and Xiaoming Sun |
|
Vol 20, Article 1 (pp 1-70)
Polynomial Identity Testing via Evaluation of Rational Functions by Ivan Hu, Dieter van Melkebeek, and Andrew Morgan |
|
Vol 19, Article 12 (pp 1-30)
Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models by Mrinal Kumar, Ramprasad Saptharishi, and Anamay Tengse |
|
Vol 19, Article 11 (pp 1-14)
A Strong XOR Lemma for Randomized Query Complexity by Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, and Hariharan Srinivasulu |
|
Vol 19, Article 10 (pp 1-44)
Separating $k$-Player from $t$-Player One-Way Communication, with Applications to Data Streams by Elbert Du, Michael Mitzenmacher, David Woodruff, and Guang Yang |
|
Vol 19, Article 7 (pp 1-51)
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$ by Yuval Filmus, Or Meir, and Avishay Tal |
|
Vol 18, Article 17 (pp 1-11)
[NOTE]
A Stochastic Calculus Approach to the Oracle Separation of $\mathsf{BQP}$ and $\mathsf{PH}$ by Xinyu Wu |
|
Vol 18, Article 13 (pp 1-65)
[RANDOM18 Spec Issue]
Round Complexity Versus Randomness Complexity in Interactive Proofs by Maya Leshkowitz |
|
Vol 18, Article 12 (pp 1-25)
From Local to Robust Testing via Agreement Testing by Irit Dinur, Prahladh Harsha, Tali Kaufman, and Noga Ron-Zewi |
|
Vol 18, Article 11 (pp 1-49)
Span Programs and Quantum Space Complexity by Stacey Jeffery |
|
Vol 18, Article 10 (pp 1-12)
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines by Emanuele Viola |
|
Vol 18, Article 4 (pp 1-46)
[APRX-RND19 Spec Issue]
Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas by Rocco A. Servedio and Li-Yang Tan |
|
Vol 18, Article 3 (pp 1-29)
[APRX-RND16 Spec Issue]
Near-Optimal NP-Hardness of Approximating Max $k$-CSP$_R$ by Pasin Manurangsi, Preetum Nakkiran, and Luca Trevisan |
|
Vol 18, Article 2 (pp 1-18)
[RANDOM18 Spec Issue]
Sunflowers and Robust Sunflowers from Randomness Extractors by Xin Li, Shachar Lovett, and Jiapeng Zhang |
|
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 |
|
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 |
|
Vol 16, Article 13 (pp 1-30)
Monotone Circuit Lower Bounds from Resolution by Ankit Garg, Mika Göös, Pritish Kamath, and Dmitry Sokolov |
|
Vol 16, Article 7 (pp 1-50)
More on Bounded Independence Plus Noise: Pseudorandom Generators for Read-Once Polynomials by Chin Ho Lee and Emanuele Viola |
|
Vol 15, Article 17 (pp 1-20)
Separation of AC$^0[\oplus]$ Formulas and Circuits by Ben Rossman and Srikanth Srinivasan |
|
Vol 14, Article 5 (pp 1-27)
Randomized Query Complexity of Sabotaged and Composed Functions by Shalev Ben-David and Robin Kothari |
|
Vol 13, Article 10 (pp 1-19)
On the Hardness of Approximating Balanced Homogenous 3-Lin by Johan Håstad and Rajsekar Manokaran |
|
Vol 12, Article 9 (pp 1-23)
[APRX-RND14 Spec Issue]
Communication Complexity of Set-Disjointness for All Probabilities by Mika Göös and Thomas Watson |
|
Vol 11, Article 14 (pp 357-393)
Non-Commutative Arithmetic Circuits with Division by Pavel Hrubeš and Avi Wigderson |