Articles under category:
Complexity Theory
ToC Library Graduate Surveys 4 (2011) 27 pages
Variations on the Sensitivity Conjecture
by Pooya Hatami, Raghav Kulkarni, and Denis Pankratov
ToC Library Graduate Surveys 3 (2011) 15 pages
Selected Results in Additive Combinatorics: An Exposition
by Emanuele Viola
ToC Library Graduate Surveys 1 (2008) 20 pages
A Brief Introduction to Fourier Analysis on the Boolean Cube
by Ronald de Wolf
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
by Sangxia Huang
Vol 10, Article 9 (pp 217-236)
Improved Inapproximability for TSP
by Michael Lampis
Vol 10, Article 8 (pp 199-215)
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata
by Eric Allender and Klaus-Jörn Lange
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
by Scott Aaronson and Andris Ambainis
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
by Aram W. Harrow, Alexandra Kolla, and Leonard J. Schulman
Vol 10, Article 2 (pp 27-53)
A Regularity Lemma and Low-Weight Approximators for Low-Degree Polynomial Threshold Functions
by Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, and Andrew Wan
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
by Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola
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
by Ola Svensson
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
by Cenny Wenner
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
by Venkatesan Guruswami and Ali Kemal Sinop
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 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
by Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff
Vol 9, Article 6 (pp 273-282) [NOTE]
The Complexity of the Fermionant and Immanants of Constant Width
by Stephan Mertens and Cristopher Moore
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
by Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki
Vol 8, Article 17 (pp 375-400)
On the Power of a Unique Quantum Witness
by Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, and Shengyu Zhang
Vol 8, Article 16 (pp 369-374) [NOTE]
Quantum Private Information Retrieval with Sublinear Communication Complexity
by François Le Gall
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 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
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 13 (pp 185-188) [NOTE]
Computing Polynomials with Few Multiplications
by Shachar Lovett
Vol 7, Article 12 (pp 177-184) [NOTE]
On Circuit Lower Bounds from Derandomization
by Scott Aaronson and Dieter van Melkebeek
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
by Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie
Vol 7, Article 4 (pp 45-48) [NOTE]
Tight Bounds on the Average Sensitivity of k-CNF
by Kazuyuki Amano
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 4 (pp 81-84) [NOTE]
Decision Trees and Influence: an Inductive Proof of the OSSS Inequality
by Homin K. Lee
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 10 (pp 191-216)
Distribution-Free Testing Lower Bound for Basic Boolean Functions
by Dana Glasner and Rocco A. Servedio
Vol 5, Article 8 (pp 141-172)
Parallel Repetition: Simplification and the No-Signaling Case
by Thomas Holenstein
Vol 5, Article 7 (pp 135-140) [NOTE]
A Simple Proof of Toda's Theorem
by Lance Fortnow
Vol 5, Article 3 (pp 69-82)
Unconditional Pseudorandom Generators for Low Degree Polynomials
by Shachar Lovett
Vol 5, Article 1 (pp 1-42)
The Power of Unentanglement
by Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor
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
by Luca Trevisan
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 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
by Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, and Alasdair Urquhart
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
by Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi
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 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
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
Vol 1, Article 1 (pp 1-28)
Limitations of Quantum Advice and One-Way Communication
by Scott Aaronson