|
Volume 4, Article 7 (pages 137-168)
Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols by Emanuele Viola and Avi Wigderson |
|
Volume 4, Article 6 (pages 129-135)
The One-Way Communication Complexity of Hamming Distance by T. S. Jayram, Ravi Kumar, and D. Sivakumar |
|
Volume 4, Article 2 (pages 21-51)
Optimal lower bounds for the Korkine-Zolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem by Miklós Ajtai |
|
Volume 3, Article 12 (pages 221-238)
An Ω(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval by Alexander Razborov and Sergey Yekhanin |
|
Volume 3, Article 8 (pages 159-177)
Removing Degeneracy May Require a Large Dimension Increase by Jiří Matoušek and Petr Škovroň |
|
Volume 3, Article 7 (pages 129-157)
Quantum Versus Classical Proofs and Advice by Scott Aaronson and Greg Kuperberg |
|
Volume 3, Article 5 (pages 81-102)
An Exponential Separation between Regular and General Resolution by Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, and Alasdair Urquhart |
|
Volume 2, Article 9 (pages 173-183)
Tolerant Versus Intolerant Testing for Boolean Properties by Eldar Fischer and Lance Fortnow |
|
Volume 2, Article 6 (pages 121-135)
Separation of Multilinear Circuit and Formula Size by Ran Raz |
|
Volume 2, Article 4 (pages 65-90)
Rank Bounds and Integrality Gaps for Cutting Planes Procedures by Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi |
|
Volume 2, Article 1 (pages 1-18)
All Quantum Adversary Methods are Equivalent by Robert Špalek and Mario Szegedy |
|
Volume 1, Article 9 (pages 177-216)
Linear Equations, Arithmetic Progressions and Hypergraph Property Testing by Noga Alon and Asaf Shapira |
|
Volume 1, Article 8 (pages 149-176)
A Non-linear Time Lower Bound for Boolean Branching Programs by Miklós Ajtai |
|
Volume 1, Article 4 (pages 47-79)
Quantum Search of Spatial Regions by Scott Aaronson and Andris Ambainis |
|
Volume 1, Article 3 (pages 37-46)
Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range by Andris Ambainis |
|
Volume 1, Article 2 (pages 29-36)
Quantum Lower Bound for the Collision Problem with Small Range by Samuel Kutin |