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 18, Article 10 (pp 1-12)
Pseudorandom Bits and Lower Bounds for Randomized Turing Machines by Emanuele Viola |
Vol 17, Article 11 (pp 1-38)
[CCC19 Spec Issue]
Hardness Magnification Near State-of-the-Art Lower Bounds by Igor C. Oliveira, Ján Pich, and Rahul Santhanam |
Vol 17, Article 10 (pp 1-88)
[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 1-27)
New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs by Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi |
Vol 17, Article 2 (pp 1-32)
[CCC19 Spec Issue]
Barriers for Fast Matrix Multiplication from Irreversibility by Matthias Christandl, Péter Vrana, and Jeroen Zuiddam |
Vol 17, Article 1 (pp 1-30)
[CCC19 Spec Issue]
Limits on the Universal Method for Matrix Multiplication by Josh Alman |
Vol 16, Article 14 (pp 1-8)
[NOTE]
On the Hardness of Approximating the $k$-Way Hypergraph Cut problem by Chandra Chekuri and Shi Li |
Vol 16, Article 9 (pp 1-12)
On the Complexity of Computing a Random Boolean Function Over the Reals by Pavel Hrubeš |
Vol 16, Article 4 (pp 1-50)
[CCC18 Spec Issue]
On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product by Lijie Chen |
Vol 16, Article 3 (pp 1-36)
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps by Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, and C. Seshadhri |
Vol 15, Article 19 (pp 1-25)
The Threshold for Subgroup Profiles to Agree is Logarithmic by James B. Wilson |
Vol 15, Article 18 (pp 1-9)
Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds by Emanuele Viola |
Vol 15, Article 17 (pp 1-20)
Separation of AC$^0[\oplus]$ Formulas and Circuits by Ben Rossman and Srikanth Srinivasan |
Vol 15, Article 13 (pp 1-34)
Closure Results for Polynomial Factorization by Chi-Ning Chou, Mrinal Kumar, and Noam Solomon |
Vol 15, Article 8 (pp 1-7)
[NOTE]
Matrix Rigidity and the Croot-Lev-Pach Lemma by Zeev Dvir and Benjamin L. Edelman |
Vol 15, Article 2 (pp 1-31)
Time Bounds for Streaming Problems by Raphaël Clifford, Markus Jalsenius, and Benjamin Sach |
Vol 14, Article 22 (pp 1-17)
On Multiparty Communication with Large versus Unbounded Error by Alexander A. Sherstov |
Vol 14, Article 21 (pp 1-23)
Separation of Unbounded-Error Models in Multi-Party Communication Complexity by Arkadev Chattopadhyay and Nikhil S. Mande |
Vol 14, Article 20 (pp 1-29)
Simplified Separation of Information and Communication by Anup Rao and Makrand Sinha |
Vol 14, Article 19 (pp 1-46)
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 1-45)
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 1-25)
New Algorithms and Lower Bounds for Circuits With Linear Threshold Gates by R. Ryan Williams |
Vol 14, Article 16 (pp 1-46)
On the Size of Homogeneous and of Depth-Four Formulas with Low Individual Degree by Neeraj Kayal, Chandan Saha, and Sébastien Tavenas |
Vol 14, Article 12 (pp 1-24)
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 1-55)
[CCC16 Spec Issue]
Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits by Ruiwen Chen, Rahul Santhanam, 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 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 |