Articles under category:
Complexity Theory
 ToC Library Graduate Surveys 9 (2020) 100 pages A Survey on Distribution Testing: Your Data is Big. But is it Blue?
 ToC Library Graduate Surveys 8 (2017) 55 pages Additive Combinatorics and its Applications in Theoretical Computer Science
 ToC Library Graduate Surveys 7 (2016) 81 pages A Survey of Quantum Property Testing
 ToC Library Graduate Surveys 4 (2011) 27 pages Variations on the Sensitivity Conjecture
 ToC Library Graduate Surveys 3 (2011) 15 pages Selected Results in Additive Combinatorics: An Exposition
 ToC Library Graduate Surveys 1 (2008) 20 pages A Brief Introduction to Fourier Analysis on the Boolean Cube
 Vol 18, Article 16 (pp 1-54) Tensor Network Complexity of Multilinear Maps by Per Austrin, Petteri Kaski, and Kaie Kubjas
 Vol 18, Article 15 (pp 1-33) [CCC20 Spec Issue] Multiparty Karchmer-Wigderson Games and Threshold Circuits
 Vol 18, Article 14 (pp 1-4) [CCC20 Spec Issue] Special Issue: CCC 2020: Guest Editors' Foreword by Zeev Dvir and Avishay Tal
 Vol 18, Article 8 (pp 1-18) [CCC18 Spec Issue] The Cayley Semigroup Membership Problem
 Vol 18, Article 5 (pp 1-28) [CCC19 Spec Issue] UG-hardness to NP-hardness by Losing Half by Amey Bhangale and Subhash Khot
 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
 Vol 17, Article 9 (pp 1-30) [CCC19 Spec Issue] Sherali--Adams Strikes Back by Ryan O'Donnell and Tselil Schramm
 Vol 17, Article 8 (pp 1-28) The Layer Complexity of Arthur-Merlin-like Communication
 Vol 17, Article 6 (pp 1-57) Almost Polynomial Hardness of Node-Disjoint Paths in Grids
 Vol 17, Article 2 (pp 1-32) [CCC19 Spec Issue] Barriers for Fast Matrix Multiplication from Irreversibility
 Vol 17, Article 1 (pp 1-30) [CCC19 Spec Issue] Limits on the Universal Method for Matrix Multiplication
 Vol 16, Article 20 (pp 1-48) [CCC19 Spec Issue] Fourier and Circulant Matrices are Not Rigid by Zeev Dvir and Allen Liu
 Vol 16, Article 19 (pp 1-5) [CCC19 Spec Issue] Special Issue: CCC 2019: Guest Editor's Foreword
 Vol 16, Article 16 (pp 1-30) A Characterization of Hard-to-Cover CSPs by Amey Bhangale, Prahladh Harsha, and Girish Varma
 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
 Vol 16, Article 8 (pp 1-55) Inaccessible Entropy II: IE Functions and Universal One-Way Hashing
 Vol 16, Article 4 (pp 1-50) [CCC18 Spec Issue] On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product
 Vol 16, Article 2 (pp 1-18) Threshold Secret Sharing Requires a Linear-Size Alphabet by Andrej Bogdanov, Siyao Guo, and Ilan Komargodski
 Vol 15, Article 19 (pp 1-25) The Threshold for Subgroup Profiles to Agree is Logarithmic
 Vol 15, Article 18 (pp 1-9) Lower Bounds for Data Structures with Space Close to Maximum Imply Circuit Lower Bounds
 Vol 15, Article 16 (pp 1-30) [CCC18 Spec Issue] Algebraic Dependencies and PSPACE Algorithms in Approximative Complexity over Any Field by Zeyu Guo, Nitin Saxena, and Amit Sinhababu
 Vol 15, Article 13 (pp 1-34) Closure Results for Polynomial Factorization by Chi-Ning Chou, Mrinal Kumar, and Noam Solomon
 Vol 15, Article 11 (pp 1-13) Fourier Sparsity and Dimension
 Vol 15, Article 10 (pp 1-26) [CCC18 Spec Issue] Pseudorandom Generators from Polarizing Random Walks
 Vol 15, Article 9 (pp 1-3) [CCC18 Spec Issue] Special Issue: CCC 2018: Guest Editor's Foreword
 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 7 (pp 1-36) Randomized Polynomial-Time Identity Testing for Noncommutative Circuits
 Vol 15, Article 2 (pp 1-31) Time Bounds for Streaming Problems
 Vol 15, Article 1 (pp 1-55) Testing $k$-Monotonicity: The Rise and Fall of Boolean Functions
 Vol 14, Article 22 (pp 1-17) On Multiparty Communication with Large versus Unbounded Error
 Vol 14, Article 21 (pp 1-23) Separation of Unbounded-Error Models in Multi-Party Communication Complexity
 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
 Vol 14, Article 18 (pp 1-45) Succinct Hitting Sets and Barriers to Proving Lower Bounds for Algebraic Circuits
 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 13 (pp 1-17) On the Hardness of Learning With Errors with Binary Secrets
 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 11 (pp 1-37) How to Verify a Quantum Computation
 Vol 14, Article 9 (pp 1-55) [CCC16 Spec Issue] Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
 Vol 14, Article 8 (pp 1-35) The Complexity of Computing the Optimal Composition of Differential Privacy by Jack Murtagh and Salil Vadhan
 Vol 14, Article 6 (pp 1-73) [CCC17 Spec Issue] Trading Information Complexity for Error by Yuval Dagan, Yuval Filmus, Hamed Hatami, and Yaqiao Li
 Vol 14, Article 2 (pp 1-2) [CCC17 Spec Issue] Special Issue: CCC 2017: Guest Editor's Foreword by Shachar Lovett and Ryan O'Donnell
 Vol 13, Article 20 (pp 1-25) The Inapproximability of Maximum Single-Sink Unsplittable, Priority and Confluent Flow Problems
 Vol 13, Article 18 (pp 1-15) Monotone Projection Lower Bounds from Extended Formulation Lower Bounds
 Vol 13, Article 16 (pp 1-23) Some Limitations of the Sum of Small-Bias Distributions by Chin Ho Lee and Emanuele Viola
 Vol 13, Article 15 (pp 1-24) Tight Hardness of the Non-Commutative Grothendieck Problem by Jop Briët, Oded Regev, and Rishi Saket
 Vol 13, Article 12 (pp 1-50) [APRX-RND14 Spec Issue] Pseudorandomness and Fourier-Growth Bounds for Width-3 Branching Programs by Thomas Steinke, Salil Vadhan, and Andrew Wan
 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 9 (pp 1-34) The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
 Vol 13, Article 7 (pp 1-18) A Communication Game Related to the Sensitivity Conjecture by Justin Gilmer, Michal Koucký, and Michael Saks
 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 13, Article 3 (pp 1-24) [APRX-RND15 Spec Issue] Towards a Characterization of Approximation Resistance for Symmetric CSPs
 Vol 13, Article 2 (pp 1-21) [CCC16 Spec Issue] Identity Testing for Constant-Width, and Any-Order, Read-Once Oblivious Arithmetic Branching Programs by Rohit Gurjar, Arpita Korwar, and Nitin Saxena
 Vol 13, Article 1 (pp 1-3) [CCC16 Spec Issue] Special Issue: CCC 2016: Guest Editor's Foreword
 Vol 12, Article 20 (pp 1-25) Dichotomies in Equilibrium Computation and Membership of PLC Markets in FIXP by Jugal Garg, Ruta Mehta, and Vijay V. Vazirani
 Vol 12, Article 19 (pp 1-33) Locally Checkable Proofs in Distributed Computing by Mika Göös and Jukka Suomela
 Vol 12, Article 16 (pp 1-34) Dual Polynomials for Collision and Element Distinctness by Mark Bun and Justin Thaler
 Vol 12, Article 12 (pp 1-38) Lower Bounds for Non-Commutative Skew Circuits
 Vol 12, Article 11 (pp 1-17) Anti-concentration for Polynomials of Independent Random Variables by Raghu Meka, Oanh Nguyen, and Van Vu
 Vol 12, Article 10 (pp 1-35) Robust Lower Bounds for Communication and Stream Computation
 Vol 12, Article 6 (pp 1-11) [NOTE] Simple Proof of Hardness of Feedback Vertex Set
 Vol 12, Article 5 (pp 1-14) A Tradeoff Between Length and Width in Resolution
 Vol 12, Article 4 (pp 1-50) Majority is Stablest: Discrete and SoS by Anindya De, Elchanan Mossel, and Joe Neeman
 Vol 12, Article 3 (pp 1-42) Interactive Proofs for $\mathsf{BQP}$ via Self-Tested Graph States
 Vol 11, Article 20 (pp 491-603) The Bose-Hubbard Model is QMA-complete by Andrew M. Childs, David Gosset, and Zak Webb
 Vol 11, Article 18 (pp 445-469) [Boolean Spec Issue] On some extensions of the FKN theorem
 Vol 11, Article 11 (pp 285-298) New Lower Bounds for the Border Rank of Matrix Multiplication
 Vol 11, Article 10 (pp 257-283) [APRX-RND13 Spec Issue] On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems
 Vol 11, Article 7 (pp 221-235) [APRX-RND12 Spec Issue] The Projection Games Conjecture and the NP-Hardness of ln $n$-Approximating Set-Cover
 Vol 11, Article 6 (pp 183-219) How Hard Is It to Approximate the Jones Polynomial?
 Vol 11, Article 3 (pp 59-103) Quantum Interactive Proofs and the Complexity of Separability Testing
 Vol 11, Article 2 (pp 35-57) The Complexity of Parity Graph Homomorphism: An Initial Investigation by John Faben and Mark Jerrum
 Vol 11, Article 1 (pp 1-34) The Complexity of Deciding Statistical Properties of Samplable Distributions
 Vol 10, Article 19 (pp 515-533) Query Complexity Lower Bounds for Reconstruction of Codes
 Vol 10, Article 18 (pp 465-514) On Reconstruction and Testing of Read-Once Formulas by Amir Shpilka and Ilya Volkovich
 Vol 10, Article 17 (pp 453-464) An Optimal Lower Bound for Monotonicity Testing over Hypergrids
 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 14 (pp 359-388) Approximation Resistance on Satisfiable Instances for Sparse Predicates
 Vol 10, Article 12 (pp 297-339) Width-Parametrized SAT: Time--Space Tradeoffs
 Vol 10, Article 9 (pp 217-236) Improved Inapproximability for TSP
 Vol 10, Article 8 (pp 199-215) Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
 Vol 10, Article 7 (pp 167-197) [RESEARCH SURVEY] Matchgates Revisited by Jin-Yi Cai and Aaron Gorenstein
 Vol 10, Article 6 (pp 133-166) The Need for Structure in Quantum Speedups
 Vol 10, Article 5 (pp 107-131) Competing-Provers Protocols for Circuit Evaluation by Gillat Kol and Ran Raz
 Vol 10, Article 3 (pp 55-75) [Boolean Spec Issue] Dimension-Free $L_2$ Maximal Inequality for Spherical Means in the Hypercube
 Vol 10, Article 2 (pp 27-53) A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions
 Vol 10, Article 1 (pp 1-26) [Boolean Spec Issue] Bounding the Sensitivity of Polynomial Threshold Functions by Prahladh Harsha, Adam Klivans, and Raghu Meka
 Vol 9, Article 28 (pp 863-887) [Boolean Spec Issue] A Two-Prover One-Round Game with Strong Soundness by Subhash Khot and Muli Safra
 Vol 9, Article 26 (pp 809-843) On Beating the Hybrid Argument
 Vol 9, Article 25 (pp 783-807) [APRX-RND12 Spec Issue] A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes by Noga Ron-Zewi and Madhu Sudan
 Vol 9, Article 24 (pp 759-781) [APRX-RND12 Spec Issue] Hardness of Vertex Deletion and Project Scheduling
 Vol 9, Article 23 (pp 703-757) [APRX-RND12 Spec Issue] Circumventing $d$-to-$1$ for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four
 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 11 (pp 413-435) Improved Inapproximability Results for Maximum $k$-Colorable Subgraph
 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 9, Article 8 (pp 295-347) Testing Properties of Collections of Distributions by Reut Levi, Dana Ron, and Ronitt Rubinfeld
 Vol 9, Article 7 (pp 283-293) Pseudorandomness for Width-2 Branching Programs
 Vol 9, Article 6 (pp 273-282) [NOTE] The Complexity of the Fermionant and Immanants of Constant Width
 Vol 9, Article 4 (pp 143-252) The Computational Complexity of Linear Optics by Scott Aaronson and Alex Arkhipov
 Vol 9, Article 2 (pp 31-116) The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems by Daniel Gottesman and Sandy Irani
 Vol 9, Article 1 (pp 1-29) The Power of Nondeterminism in Self-Assembly
 Vol 8, Article 17 (pp 375-400) On the Power of a Unique Quantum Witness
 Vol 8, Article 16 (pp 369-374) [NOTE] Quantum Private Information Retrieval with Sublinear Communication Complexity
 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 10 (pp 231-238) [NOTE] Monotone Circuits: One-Way Functions versus Pseudorandom Generators by Oded Goldreich and Rani Izsak
 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 13 (pp 185-188) [NOTE] Computing Polynomials with Few Multiplications
 Vol 7, Article 12 (pp 177-184) [NOTE] On Circuit Lower Bounds from Derandomization
 Vol 7, Article 11 (pp 155-176) Distribution-Free Testing for Monomials with a Sublinear Number of Queries by Elya Dolev and Dana Ron
 Vol 7, Article 10 (pp 147-153) [NOTE] The Influence Lower Bound Via Query Elimination by Rahul Jain and Shengyu Zhang
 Vol 7, Article 8 (pp 119-129) Arithmetic Complexity in Ring Extensions by Pavel Hrubeš and Amir Yehudayoff
 Vol 7, Article 7 (pp 101-117) Quantum Interactive Proofs with Short Messages by Salman Beigi, Peter Shor, and John Watrous
 Vol 7, Article 6 (pp 75-99) Testing Linear-Invariant Non-Linear Properties
 Vol 7, Article 4 (pp 45-48) [NOTE] Tight Bounds on the Average Sensitivity of k-CNF
 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 4 (pp 81-84) [NOTE] Decision Trees and Influence: an Inductive Proof of the OSSS Inequality
 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 10 (pp 191-216) Distribution-Free Testing Lower Bound for Basic Boolean Functions
 Vol 5, Article 8 (pp 141-172) Parallel Repetition: Simplification and the No-Signaling Case
 Vol 5, Article 7 (pp 135-140) [NOTE] A Simple Proof of Toda's Theorem
 Vol 5, Article 3 (pp 69-82) Unconditional Pseudorandom Generators for Low-Degree Polynomials
 Vol 5, Article 1 (pp 1-42) The Power of Unentanglement
 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 5 (pp 111-128) Approximation Algorithms for Unique Games
 Vol 3, Article 12 (pp 221-238) An   Ω(n1/3)   Lower Bound for Bilinear Group Based Private Information Retrieval
 Vol 3, Article 11 (pp 211-219) The Randomized Communication Complexity of Set Disjointness by Johan Håstad and Avi Wigderson
 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 3, Article 4 (pp 61-79) A Simple PromiseBQP-complete Matrix Problem by Dominik Janzing and Pawel Wocjan
 Vol 3, Article 3 (pp 45-60) On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy by Ishay Haviv, Oded Regev, and Amnon Ta-Shma
 Vol 3, Article 2 (pp 25-43) Easily refutable subformulas of large random 3CNF formulas by Uriel Feige and Eran Ofek
 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 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 7 (pp 119-148) Query Efficient PCPs with Perfect Completeness by Johan Håstad and Subhash Khot
 Vol 1, Article 5 (pp 81-103) Quantum Fan-out is Powerful by Peter Høyer and Robert Špalek
 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
 Vol 1, Article 1 (pp 1-28) Limitations of Quantum Advice and One-Way Communication