Articles under category:
Lower Bounds
 Vol 14, Article 17 (pp 1-25) New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates
 Vol 14, Article 16 (pp 1-46) On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree
 Vol 14, Article 12 (pp 1-24) Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression
 Vol 14, Article 9 (pp 1-55) [CCC16 Spec Issue] Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
 Vol 14, Article 5 (pp 1-27) Randomized Query Complexity of Sabotaged and Composed Functions
 Vol 13, Article 19 (pp 1-51) [APRX-RND15 Spec Issue] Improved NP-Inapproximability for $2$-Variable Linear Equations
 Vol 13, Article 18 (pp 1-15) Monotone Projection Lower Bounds from Extended Formulation Lower Bounds
 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
 Vol 12, Article 12 (pp 1-38) Lower Bounds for Non-Commutative Skew Circuits
 Vol 12, Article 10 (pp 1-35) Robust Lower Bounds for Communication and Stream Computation
 Vol 12, Article 5 (pp 1-14) A Tradeoff Between Length and Width in Resolution
 Vol 11, Article 19 (pp 471-489) Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures
 Vol 11, Article 15 (pp 395-401) [NOTE] Groups with Identical $k$-Profiles
 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
 Vol 10, Article 17 (pp 453-464) An Optimal Lower Bound for Monotonicity Testing over Hypergrids
 Vol 10, Article 16 (pp 421-451) How Many Bits Can a Flock of Birds Compute?
 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
 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
 Vol 9, Article 9 (pp 349-401) Quantum Money from Hidden Subspaces
 Vol 8, Article 12 (pp 269-289) SDP Gaps from Pairwise Independence
 Vol 8, Article 11 (pp 239-267) Tight Bounds on the Approximability of Almost-Satisfiable Horn SAT and Exact Hitting Set
 Vol 8, Article 8 (pp 197-208) The Communication Complexity of Gap Hamming Distance ■
 Vol 8, Article 1 (pp 1-51) Time-Space Efficient Simulations of Quantum Computations
 Vol 7, Article 12 (pp 177-184) [NOTE] On Circuit Lower Bounds from Derandomization
 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
 Vol 6, Article 9 (pp 201-225) Separating Deterministic from Randomized Multiparty Communication Complexity
 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
 Vol 5, Article 13 (pp 257-282) Optimal Cryptographic Hardness of Learning Monotone Functions
 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
 Vol 3, Article 12 (pp 221-238) An   Ω(n1/3)   Lower Bound for Bilinear Group Based Private Information Retrieval
 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
 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
 Vol 2, Article 2 (pp 19-51) Proving Integrality Gaps without Knowing the Linear Program
 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
 Vol 1, Article 4 (pp 47-79) Quantum Search of Spatial Regions
 Vol 1, Article 3 (pp 37-46) Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
 Vol 1, Article 2 (pp 29-36) Quantum Lower Bound for the Collision Problem with Small Range