Articles under category:
Lower Bounds
Vol 13, Article 19 (pp 1-51) [APRX-RND15 Spec Issue]
Improved NP-Inapproximability for $2$-Variable Linear Equations
by Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright
Vol 13, Article 18 (pp 1-15)
Monotone Projection Lower Bounds from Extended Formulation Lower Bounds
by Joshua A. Grochow
Vol 13, Article 11 (pp 1-36)
Superquadratic Lower Bound for 3-Query Locally Correctable Codes over the Reals
by Zeev Dvir, Shubhangi Saraf, and Avi Wigderson
Vol 13, Article 6 (pp 1-33) [CCC16 Spec Issue]
Arithmetic Circuits with Locally Low Algebraic Rank
by Mrinal Kumar and Shubhangi Saraf
Vol 13, Article 4 (pp 1-22)
On the (Non) NP-Hardness of Computing Circuit Complexity
by Cody D. Murray and R. Ryan Williams
Vol 12, Article 12 (pp 1-38)
Lower Bounds for Non-Commutative Skew Circuits
by Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan
Vol 12, Article 10 (pp 1-35)
Robust Lower Bounds for Communication and Stream Computation
by Amit Chakrabarti, Graham Cormode, and Andrew McGregor
Vol 12, Article 5 (pp 1-14)
A Tradeoff Between Length and Width in Resolution
by Neil Thapen
Vol 11, Article 19 (pp 471-489)
Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures
by Joshua Brody and Kasper Green Larsen
Vol 11, Article 15 (pp 395-401) [NOTE]
Groups with Identical $k$-Profiles
by George Glauberman and Łukasz Grabowski
Vol 11, Article 14 (pp 357-393)
Non-Commutative Arithmetic Circuits with Division
by Pavel Hrubeš and Avi Wigderson
Vol 11, Article 11 (pp 285-298)
New Lower Bounds for the Border Rank of Matrix Multiplication
by Joseph M. Landsberg and Giorgio Ottaviani
Vol 10, Article 17 (pp 453-464)
An Optimal Lower Bound for Monotonicity Testing over Hypergrids
by Deeparnab Chakrabarty and C. Seshadhri
Vol 10, Article 16 (pp 421-451)
How Many Bits Can a Flock of Birds Compute?
by Bernard Chazelle
Vol 10, Article 15 (pp 389-419) [Boolean Spec Issue]
Tight Bounds for Monotone Switching Networks via Fourier Analysis
by Siu Man Chan and Aaron Potechin
Vol 10, Article 10 (pp 237-256)
Lower Bounds for the Average and Smoothed Number of Pareto-Optima
by Tobias Brunsch, Navin Goyal, Luis Rademacher, and Heiko Röglin
Vol 9, Article 22 (pp 685-702)
Hamming Approximation of NP Witnesses
by Daniel Sheldon and Neal E. Young
Vol 9, Article 14 (pp 471-557)
Towards an Optimal Separation of Space and Length in Resolution
by Jakob Nordström and Johan Håstad
Vol 9, Article 10 (pp 403-411)
On the Real $\tau$-Conjecture and the Distribution of Complex Roots
by Pavel Hrubeš
Vol 9, Article 9 (pp 349-401)
Quantum Money from Hidden Subspaces
by Scott Aaronson and Paul Christiano
Vol 8, Article 12 (pp 269-289)
SDP Gaps from Pairwise Independence
by Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani
Vol 8, Article 11 (pp 239-267)
Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set
by Venkatesan Guruswami and Yuan Zhou
Vol 8, Article 8 (pp 197-208)
The Communication Complexity of Gap Hamming Distance
by Alexander A. Sherstov
Vol 8, Article 1 (pp 1-51)
Time-Space Efficient Simulations of Quantum Computations
by Dieter van Melkebeek and Thomas Watson
Vol 7, Article 12 (pp 177-184) [NOTE]
On Circuit Lower Bounds from Derandomization
by Scott Aaronson and Dieter van Melkebeek
Vol 7, Article 10 (pp 147-153) [NOTE]
The Influence Lower Bound Via Query Elimination
by Rahul Jain and Shengyu Zhang
Vol 6, Article 10 (pp 227-245)
A Separation of NP and coNP in Multiparty Communication Complexity
by Dmitry Gavinsky and Alexander A. Sherstov
Vol 6, Article 9 (pp 201-225)
Separating Deterministic from Randomized Multiparty Communication Complexity
by Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel
Vol 6, Article 7 (pp 135-177)
Elusive Functions and Lower Bounds for Arithmetic Circuits
by Ran Raz
Vol 6, Article 6 (pp 113-134)
Rounds vs. Queries Tradeoff in Noisy Computation
by Navin Goyal and Michael Saks
Vol 6, Article 1 (pp 1-25)
A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search
by Andris Ambainis
Vol 5, Article 13 (pp 257-282)
Optimal Cryptographic Hardness of Learning Monotone Functions
by Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, and Hoeteck Wee
Vol 5, Article 6 (pp 125-134)
Hard Metrics from Cayley Graphs of Abelian Groups
by Ilan Newman and Yuri Rabinovich
Vol 5, Article 4 (pp 83-117)
SDP Gaps and UGC-hardness for Max-Cut-Gain
by Subhash Khot and Ryan O'Donnell
Vol 4, Article 7 (pp 137-168)
Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols
by Emanuele Viola and Avi Wigderson
Vol 4, Article 6 (pp 129-135)
The One-Way Communication Complexity of Hamming Distance
by T. S. Jayram, Ravi Kumar, and D. Sivakumar
Vol 4, Article 2 (pp 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
Vol 3, Article 12 (pp 221-238)
An   Ω(n1/3)   Lower Bound for Bilinear Group Based Private Information Retrieval
by Alexander Razborov and Sergey Yekhanin
Vol 3, Article 8 (pp 159-177)
Removing Degeneracy May Require a Large Dimension Increase
by Jiří Matoušek and Petr Škovroň
Vol 3, Article 7 (pp 129-157)
Quantum Versus Classical Proofs and Advice
by Scott Aaronson and Greg Kuperberg
Vol 3, Article 5 (pp 81-102)
An Exponential Separation between Regular and General Resolution
by Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, and Alasdair Urquhart
Vol 2, Article 9 (pp 173-183)
Tolerant Versus Intolerant Testing for Boolean Properties
by Eldar Fischer and Lance Fortnow
Vol 2, Article 6 (pp 121-135)
Separation of Multilinear Circuit and Formula Size
by Ran Raz
Vol 2, Article 4 (pp 65-90)
Rank Bounds and Integrality Gaps for Cutting Planes Procedures
by Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi
Vol 2, Article 2 (pp 19-51)
Proving Integrality Gaps without Knowing the Linear Program
by Sanjeev Arora, Béla Bollobás, László Lovász, and Iannis Tourlakis
Vol 2, Article 1 (pp 1-18)
All Quantum Adversary Methods are Equivalent
by Robert Špalek and Mario Szegedy
Vol 1, Article 9 (pp 177-216)
Linear Equations, Arithmetic Progressions and Hypergraph Property Testing
by Noga Alon and Asaf Shapira
Vol 1, Article 8 (pp 149-176)
A Non-linear Time Lower Bound for Boolean Branching Programs
by Miklós Ajtai
Vol 1, Article 4 (pp 47-79)
Quantum Search of Spatial Regions
by Scott Aaronson and Andris Ambainis
Vol 1, Article 3 (pp 37-46)
Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
by Andris Ambainis
Vol 1, Article 2 (pp 29-36)
Quantum Lower Bound for the Collision Problem with Small Range
by Samuel Kutin