Articles under category:
Lower Bounds
Lower Bounds
ToC Library Graduate Surveys 9 (2020) 100 pages
A Survey on Distribution Testing: Your Data is Big. But is it Blue? by Clément L. Canonne 
Vol 19, Article 11 (pp 114)
A Strong XOR Lemma for Randomized Query Complexity by Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, and Hariharan Srinivasulu 
Vol 19, Article 10 (pp 144)
Separating $k$Player from $t$Player OneWay Communication, with Applications to Data Streams by Elbert Du, Michael Mitzenmacher, David Woodruff, and Guang Yang 
Vol 19, Article 9 (pp 135)
Optimal Composition Theorem for Randomized Query Complexity by Dmytro Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal 
Vol 19, Article 7 (pp 151)
Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$ by Yuval Filmus, Or Meir, and Avishay Tal 
Vol 18, Article 10 (pp 112)
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines by Emanuele Viola 
Vol 17, Article 11 (pp 138)
[CCC19 Spec Issue]
Hardness Magnification Near StateoftheArt Lower Bounds by Igor C. Oliveira, Ján Pich, and Rahul Santhanam 
Vol 17, Article 10 (pp 188)
[CCC16 Spec Issue]
Proof Complexity Lower Bounds from Algebraic Circuit Complexity by Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson 
Vol 17, Article 5 (pp 127)
New Algorithms and Lower Bounds for AllPairs MaxFlow in Undirected Graphs by Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi 
Vol 17, Article 2 (pp 132)
[CCC19 Spec Issue]
Barriers for Fast Matrix Multiplication from Irreversibility by Matthias Christandl, Péter Vrana, and Jeroen Zuiddam 
Vol 17, Article 1 (pp 130)
[CCC19 Spec Issue]
Limits on the Universal Method for Matrix Multiplication by Josh Alman 
Vol 16, Article 14 (pp 18)
[NOTE]
On the Hardness of Approximating the $k$Way Hypergraph Cut problem by Chandra Chekuri and Shi Li 
Vol 16, Article 9 (pp 112)
On the Complexity of Computing a Random Boolean Function Over the Reals by Pavel Hrubeš 
Vol 16, Article 4 (pp 150)
[CCC18 Spec Issue]
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product by Lijie Chen 
Vol 16, Article 3 (pp 136)
Optimal Unateness Testers for RealValued Functions: Adaptivity Helps by Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri 
Vol 15, Article 19 (pp 125)
The Threshold for Subgroup Profiles to Agree is Logarithmic by James B. Wilson 
Vol 15, Article 18 (pp 19)
Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds by Emanuele Viola 
Vol 15, Article 17 (pp 120)
Separation of AC$^0[\oplus]$ Formulas and Circuits by Ben Rossman and Srikanth Srinivasan 
Vol 15, Article 13 (pp 134)
Closure Results for Polynomial Factorization by ChiNing Chou, Mrinal Kumar, and Noam Solomon 
Vol 15, Article 8 (pp 17)
[NOTE]
Matrix Rigidity and the CrootLevPach Lemma by Zeev Dvir and Benjamin L. Edelman 
Vol 15, Article 2 (pp 131)
Time Bounds for Streaming Problems by Raphaël Clifford, Markus Jalsenius, and Benjamin Sach 
Vol 14, Article 22 (pp 117)
On Multiparty Communication with Large versus Unbounded Error by Alexander A. Sherstov 
Vol 14, Article 21 (pp 123)
Separation of UnboundedError Models in MultiParty Communication Complexity by Arkadev Chattopadhyay and Nikhil S. Mande 
Vol 14, Article 20 (pp 129)
Simplified Separation of Information and Communication by Anup Rao and Makrand Sinha 
Vol 14, Article 19 (pp 146)
A Chasm Between Identity and Equivalence Testing with Conditional Queries by Jayadev Acharya, Clément L. Canonne, and Gautam Kamath 
Vol 14, Article 18 (pp 145)
Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits by Michael A. Forbes, Amir Shpilka, and Ben Lee Volk 
Vol 14, Article 17 (pp 125)
New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates by R. Ryan Williams 
Vol 14, Article 16 (pp 146)
On the Size of Homogeneous and of DepthFour Formulas with Low Individual Degree by Neeraj Kayal, Chandan Saha, and Sébastien Tavenas 
Vol 14, Article 12 (pp 124)
Certifying Polynomials for $\mathrm{AC}^0[\oplus]$ Circuits, with Applications to Lower Bounds and Circuit Compression by Swastik Kopparty and Srikanth Srinivasan 
Vol 14, Article 9 (pp 155)
[CCC16 Spec Issue]
AverageCase Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits by Ruiwen Chen, Rahul Santhanam, and Srikanth Srinivasan 
Vol 14, Article 5 (pp 127)
Randomized Query Complexity of Sabotaged and Composed Functions by Shalev BenDavid and Robin Kothari 
Vol 13, Article 19 (pp 151)
[APRXRND15 Spec Issue]
Improved NPInapproximability for $2$Variable Linear Equations by Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, and John Wright 
Vol 13, Article 18 (pp 115)
Monotone Projection Lower Bounds from Extended Formulation Lower Bounds by Joshua A. Grochow 
Vol 13, Article 11 (pp 136)
Superquadratic Lower Bound for 3Query Locally Correctable Codes over the Reals by Zeev Dvir, Shubhangi Saraf, and Avi Wigderson 
Vol 13, Article 6 (pp 133)
[CCC16 Spec Issue]
Arithmetic Circuits with Locally Low Algebraic Rank by Mrinal Kumar and Shubhangi Saraf 
Vol 13, Article 4 (pp 122)
On the (Non) NPHardness of Computing Circuit Complexity by Cody D. Murray and R. Ryan Williams 
Vol 12, Article 12 (pp 138)
Lower Bounds for NonCommutative Skew Circuits by Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan 
Vol 12, Article 10 (pp 135)
Robust Lower Bounds for Communication and Stream Computation by Amit Chakrabarti, Graham Cormode, and Andrew McGregor 
Vol 12, Article 5 (pp 114)
A Tradeoff Between Length and Width in Resolution by Neil Thapen 
Vol 11, Article 19 (pp 471489)
Adapt or Die: Polynomial Lower Bounds for NonAdaptive Dynamic Data Structures by Joshua Brody and Kasper Green Larsen 
Vol 11, Article 15 (pp 395401)
[NOTE]
Groups with Identical $k$Profiles by George Glauberman and Łukasz Grabowski 
Vol 11, Article 14 (pp 357393)
NonCommutative Arithmetic Circuits with Division by Pavel Hrubeš and Avi Wigderson 
Vol 11, Article 11 (pp 285298)
New Lower Bounds for the Border Rank of Matrix Multiplication by Joseph M. Landsberg and Giorgio Ottaviani 
Vol 10, Article 17 (pp 453464)
An Optimal Lower Bound for Monotonicity Testing over Hypergrids by Deeparnab Chakrabarty and C. Seshadhri 
Vol 10, Article 16 (pp 421451)
How Many Bits Can a Flock of Birds Compute? by Bernard Chazelle 
Vol 10, Article 15 (pp 389419)
[Boolean Spec Issue]
Tight Bounds for Monotone Switching Networks via Fourier Analysis by Siu Man Chan and Aaron Potechin 
Vol 10, Article 10 (pp 237256)
Lower Bounds for the Average and Smoothed Number of ParetoOptima by Tobias Brunsch, Navin Goyal, Luis Rademacher, and Heiko Röglin 
Vol 9, Article 22 (pp 685702)
Hamming Approximation of NP Witnesses by Daniel Sheldon and Neal E. Young 
Vol 9, Article 14 (pp 471557)
Towards an Optimal Separation of Space and Length in Resolution by Jakob Nordström and Johan Håstad 
Vol 9, Article 10 (pp 403411)
On the Real $\tau$Conjecture and the Distribution of Complex Roots by Pavel Hrubeš 
Vol 9, Article 9 (pp 349401)
Quantum Money from Hidden Subspaces by Scott Aaronson and Paul Christiano 
Vol 8, Article 12 (pp 269289)
SDP Gaps from Pairwise Independence by Siavosh Benabbas, Konstantinos Georgiou, Avner Magen, and Madhur Tulsiani 
Vol 8, Article 11 (pp 239267)
Tight Bounds on the Approximability of AlmostSatisfiable Horn SAT and Exact Hitting Set by Venkatesan Guruswami and Yuan Zhou 
Vol 8, Article 8 (pp 197208)
The Communication Complexity of Gap Hamming Distance by Alexander A. Sherstov 
■

Vol 8, Article 1 (pp 151)
TimeSpace Efficient Simulations of Quantum Computations by Dieter van Melkebeek and Thomas Watson 
Vol 7, Article 12 (pp 177184)
[NOTE]
On Circuit Lower Bounds from Derandomization by Scott Aaronson and Dieter van Melkebeek 
Vol 7, Article 10 (pp 147153)
[NOTE]
The Influence Lower Bound Via Query Elimination by Rahul Jain and Shengyu Zhang 
Vol 6, Article 10 (pp 227245)
A Separation of NP and coNP in Multiparty Communication Complexity by Dmitry Gavinsky and Alexander A. Sherstov 
Vol 6, Article 9 (pp 201225)
Separating Deterministic from Randomized Multiparty Communication Complexity by Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel 
Vol 6, Article 7 (pp 135177)
Elusive Functions and Lower Bounds for Arithmetic Circuits by Ran Raz 
Vol 6, Article 6 (pp 113134)
Rounds vs. Queries Tradeoff in Noisy Computation by Navin Goyal and Michael Saks 
Vol 6, Article 1 (pp 125)
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 257282)
Optimal Cryptographic Hardness of Learning Monotone Functions by Dana DachmanSoled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, and Hoeteck Wee 
Vol 5, Article 6 (pp 125134)
Hard Metrics from Cayley Graphs of Abelian Groups by Ilan Newman and Yuri Rabinovich 
Vol 5, Article 4 (pp 83117)
SDP Gaps and UGChardness for MaxCutGain by Subhash Khot and Ryan O'Donnell 
Vol 4, Article 7 (pp 137168)
Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols by Emanuele Viola and Avi Wigderson 
Vol 4, Article 6 (pp 129135)
The OneWay Communication Complexity of Hamming Distance by T. S. Jayram, Ravi Kumar, and D. Sivakumar 
Vol 4, Article 2 (pp 2151)
Optimal lower bounds for the KorkineZolotareff parameters of a lattice and for Schnorr's algorithm for the shortest vector problem by Miklós Ajtai 
Vol 3, Article 12 (pp 221238)
An Ω(n^{1/3}) Lower Bound for Bilinear Group Based Private Information Retrieval by Alexander Razborov and Sergey Yekhanin 
Vol 3, Article 8 (pp 159177)
Removing Degeneracy May Require a Large Dimension Increase by Jiří Matoušek and Petr Škovroň 
Vol 3, Article 7 (pp 129157)
Quantum Versus Classical Proofs and Advice by Scott Aaronson and Greg Kuperberg 
Vol 3, Article 5 (pp 81102)
An Exponential Separation between Regular and General Resolution by Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, and Alasdair Urquhart 
Vol 2, Article 9 (pp 173183)
Tolerant Versus Intolerant Testing for Boolean Properties by Eldar Fischer and Lance Fortnow 
Vol 2, Article 6 (pp 121135)
Separation of Multilinear Circuit and Formula Size by Ran Raz 
Vol 2, Article 4 (pp 6590)
Rank Bounds and Integrality Gaps for Cutting Planes Procedures by Joshua BureshOppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi 
Vol 2, Article 2 (pp 1951)
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 118)
All Quantum Adversary Methods are Equivalent by Robert Špalek and Mario Szegedy 
Vol 1, Article 9 (pp 177216)
Linear Equations, Arithmetic Progressions and Hypergraph Property Testing by Noga Alon and Asaf Shapira 
Vol 1, Article 8 (pp 149176)
A Nonlinear Time Lower Bound for Boolean Branching Programs by Miklós Ajtai 
Vol 1, Article 4 (pp 4779)
Quantum Search of Spatial Regions by Scott Aaronson and Andris Ambainis 
Vol 1, Article 3 (pp 3746)
Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range by Andris Ambainis 
Vol 1, Article 2 (pp 2936)
Quantum Lower Bound for the Collision Problem with Small Range by Samuel Kutin 