Articles under category:
Complexity Theory
Complexity Theory
ToC Library Graduate Surveys 8 (2017) 55 pages
Additive Combinatorics and its Applications in Theoretical Computer Science by Shachar Lovett 
ToC Library Graduate Surveys 7 (2016) 81 pages
A Survey of Quantum Property Testing by Ashley Montanaro and Ronald de Wolf 
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 15, Article 1 (pp 155)
Testing $k$Monotonicity: The Rise and Fall of Boolean Functions by Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer 
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 13 (pp 117)
On the Hardness of Learning With Errors with Binary Secrets by Daniele Micciancio 
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 11 (pp 137)
How to Verify a Quantum Computation by Anne Broadbent 
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 8 (pp 135)
The Complexity of Computing the Optimal Composition of Differential Privacy by Jack Murtagh and Salil Vadhan 
Vol 14, Article 6 (pp 173)
[CCC17 Spec Issue]
Trading Information Complexity for Error by Yuval Dagan, Yuval Filmus, Hamed Hatami, and Yaqiao Li 
Vol 14, Article 2 (pp 12)
[CCC17 Spec Issue]
Special Issue: CCC 2017: Guest Editor's Foreword by Shachar Lovett and Ryan O'Donnell 
Vol 13, Article 20 (pp 125)
The Inapproximability of Maximum SingleSink Unsplittable, Priority and Confluent Flow Problems by F. Bruce Shepherd and Adrian R. Vetta 
Vol 13, Article 18 (pp 115)
Monotone Projection Lower Bounds from Extended Formulation Lower Bounds by Joshua A. Grochow 
Vol 13, Article 16 (pp 123)
Some Limitations of the Sum of SmallBias Distributions by Chin Ho Lee and Emanuele Viola 
Vol 13, Article 15 (pp 124)
Tight Hardness of the NonCommutative Grothendieck Problem by Jop Briët, Oded Regev, and Rishi Saket 
Vol 13, Article 12 (pp 150)
[APRXRND14 Spec Issue]
Pseudorandomness and FourierGrowth Bounds for Width3 Branching Programs by Thomas Steinke, Salil Vadhan, and Andrew Wan 
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 9 (pp 134)
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials by Hervé Fournier, Nutan Limaye, Meena Mahajan, and Srikanth Srinivasan 
Vol 13, Article 7 (pp 118)
A Communication Game Related to the Sensitivity Conjecture by Justin Gilmer, Michal Koucký, and Michael Saks 
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 13, Article 3 (pp 124)
[APRXRND15 Spec Issue]
Towards a Characterization of Approximation Resistance for Symmetric CSPs by Venkatesan Guruswami and Euiwoong Lee 
Vol 13, Article 2 (pp 121)
[CCC16 Spec Issue]
Identity Testing for ConstantWidth, and AnyOrder, ReadOnce Oblivious Arithmetic Branching Programs by Rohit Gurjar, Arpita Korwar, and Nitin Saxena 
Vol 13, Article 1 (pp 13)
[CCC16 Spec Issue]
Special Issue: CCC 2016: Guest Editor's Foreword by Prahladh Harsha 
Vol 12, Article 20 (pp 125)
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 133)
Locally Checkable Proofs in Distributed Computing by Mika Göös and Jukka Suomela 
Vol 12, Article 16 (pp 134)
Dual Polynomials for Collision and Element Distinctness by Mark Bun and Justin Thaler 
Vol 12, Article 12 (pp 138)
Lower Bounds for NonCommutative Skew Circuits by Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan 
Vol 12, Article 11 (pp 117)
Anticoncentration for Polynomials of Independent Random Variables by Raghu Meka, Oanh Nguyen, and Van Vu 
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 6 (pp 111)
[NOTE]
Simple Proof of Hardness of Feedback Vertex Set by Venkatesan Guruswami and Euiwoong Lee 
Vol 12, Article 5 (pp 114)
A Tradeoff Between Length and Width in Resolution by Neil Thapen 
Vol 12, Article 4 (pp 150)
Majority is Stablest: Discrete and SoS by Anindya De, Elchanan Mossel, and Joe Neeman 
Vol 12, Article 3 (pp 142)
Interactive Proofs for $\mathsf{BQP}$ via SelfTested Graph States by Matthew McKague 
Vol 11, Article 20 (pp 491603)
The BoseHubbard Model is QMAcomplete by Andrew M. Childs, David Gosset, and Zak Webb 
Vol 11, Article 18 (pp 445469)
[Boolean Spec Issue]
On some extensions of the FKN theorem by Jacek Jendrej, Krzysztof Oleszkiewicz, and Jakub O. Wojtaszczyk 
Vol 11, Article 11 (pp 285298)
New Lower Bounds for the Border Rank of Matrix Multiplication by Joseph M. Landsberg and Giorgio Ottaviani 
Vol 11, Article 10 (pp 257283)
[APRXRND13 Spec Issue]
On the NPHardness of Approximating OrderingConstraint Satisfaction Problems by Per Austrin, Rajsekar Manokaran, and Cenny Wenner 
Vol 11, Article 7 (pp 221235)
[APRXRND12 Spec Issue]
The Projection Games Conjecture and the NPHardness of ln $n$Approximating SetCover by Dana Moshkovitz 
Vol 11, Article 6 (pp 183219)
How Hard Is It to Approximate the Jones Polynomial? by Greg Kuperberg 
Vol 11, Article 3 (pp 59103)
Quantum Interactive Proofs and the Complexity of Separability Testing by Gus Gutoski, Patrick Hayden, Kevin Milner, and Mark M. Wilde 
Vol 11, Article 2 (pp 3557)
The Complexity of Parity Graph Homomorphism: An Initial Investigation by John Faben and Mark Jerrum 
Vol 11, Article 1 (pp 134)
The Complexity of Deciding Statistical Properties of Samplable Distributions by Thomas Watson 
Vol 10, Article 19 (pp 515533)
Query Complexity Lower Bounds for Reconstruction of Codes by Sourav Chakraborty, Eldar Fischer, and Arie Matsliah 
Vol 10, Article 18 (pp 465514)
On Reconstruction and Testing of ReadOnce Formulas by Amir Shpilka and Ilya Volkovich 
Vol 10, Article 17 (pp 453464)
An Optimal Lower Bound for Monotonicity Testing over Hypergrids by Deeparnab Chakrabarty and C. Seshadhri 
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 14 (pp 359388)
Approximation Resistance on Satisfiable Instances for Sparse Predicates by Sangxia Huang 
Vol 10, Article 12 (pp 297339)
WidthParametrized SAT: TimeSpace Tradeoffs by Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang 
Vol 10, Article 9 (pp 217236)
Improved Inapproximability for TSP by Michael Lampis 
Vol 10, Article 8 (pp 199215)
Symmetry Coincides with Nondeterminism for TimeBounded Auxiliary Pushdown Automata by Eric Allender and KlausJörn Lange 
Vol 10, Article 7 (pp 167197)
[RESEARCH SURVEY]
Matchgates Revisited by JinYi Cai and Aaron Gorenstein 
Vol 10, Article 6 (pp 133166)
The Need for Structure in Quantum Speedups by Scott Aaronson and Andris Ambainis 
Vol 10, Article 5 (pp 107131)
CompetingProvers Protocols for Circuit Evaluation by Gillat Kol and Ran Raz 
Vol 10, Article 3 (pp 5575)
[Boolean Spec Issue]
DimensionFree $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 2753)
A Regularity Lemma and LowWeight Approximators for LowDegree Polynomial Threshold Functions by Ilias Diakonikolas, Rocco A. Servedio, LiYang Tan, and Andrew Wan 
Vol 10, Article 1 (pp 126)
[Boolean Spec Issue]
Bounding the Sensitivity of Polynomial Threshold Functions by Prahladh Harsha, Adam Klivans, and Raghu Meka 
Vol 9, Article 28 (pp 863887)
[Boolean Spec Issue]
A TwoProver OneRound Game with Strong Soundness by Subhash Khot and Muli Safra 
Vol 9, Article 26 (pp 809843)
On Beating the Hybrid Argument by Bill Fefferman, Ronen Shaltiel, Christopher Umans, and Emanuele Viola 
Vol 9, Article 25 (pp 783807)
[APRXRND12 Spec Issue]
A New Upper Bound on the Query Complexity of Testing Generalized ReedMuller Codes by Noga RonZewi and Madhu Sudan 
Vol 9, Article 24 (pp 759781)
[APRXRND12 Spec Issue]
Hardness of Vertex Deletion and Project Scheduling by Ola Svensson 
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 11 (pp 413435)
Improved Inapproximability Results for Maximum $k$Colorable Subgraph by Venkatesan Guruswami and Ali Kemal Sinop 
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 9, Article 8 (pp 295347)
Testing Properties of Collections of Distributions by Reut Levi, Dana Ron, and Ronitt Rubinfeld 
Vol 9, Article 7 (pp 283293)
Pseudorandomness for Width2 Branching Programs by Andrej Bogdanov, Zeev Dvir, Elad Verbin, and Amir Yehudayoff 
Vol 9, Article 6 (pp 273282)
[NOTE]
The Complexity of the Fermionant and Immanants of Constant Width by Stephan Mertens and Cristopher Moore 
Vol 9, Article 4 (pp 143252)
The Computational Complexity of Linear Optics by Scott Aaronson and Alex Arkhipov 
Vol 9, Article 2 (pp 31116)
The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems by Daniel Gottesman and Sandy Irani 
Vol 9, Article 1 (pp 129)
The Power of Nondeterminism in SelfAssembly by Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki 
Vol 8, Article 17 (pp 375400)
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 369374)
[NOTE]
Quantum Private Information Retrieval with Sublinear Communication Complexity by François Le Gall 
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 10 (pp 231238)
[NOTE]
Monotone Circuits: OneWay Functions versus Pseudorandom Generators by Oded Goldreich and Rani Izsak 
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 13 (pp 185188)
[NOTE]
Computing Polynomials with Few Multiplications by Shachar Lovett 
Vol 7, Article 12 (pp 177184)
[NOTE]
On Circuit Lower Bounds from Derandomization by Scott Aaronson and Dieter van Melkebeek 
Vol 7, Article 11 (pp 155176)
DistributionFree Testing for Monomials with a Sublinear Number of Queries by Elya Dolev and Dana Ron 
Vol 7, Article 10 (pp 147153)
[NOTE]
The Influence Lower Bound Via Query Elimination by Rahul Jain and Shengyu Zhang 
Vol 7, Article 8 (pp 119129)
Arithmetic Complexity in Ring Extensions by Pavel Hrubeš and Amir Yehudayoff 
Vol 7, Article 7 (pp 101117)
Quantum Interactive Proofs with Short Messages by Salman Beigi, Peter Shor, and John Watrous 
Vol 7, Article 6 (pp 7599)
Testing LinearInvariant NonLinear Properties by Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie 
Vol 7, Article 4 (pp 4548)
[NOTE]
Tight Bounds on the Average Sensitivity of kCNF by Kazuyuki Amano 
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 4 (pp 8184)
[NOTE]
Decision Trees and Influence: an Inductive Proof of the OSSS Inequality by Homin K. Lee 
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 10 (pp 191216)
DistributionFree Testing Lower Bound for Basic Boolean Functions by Dana Glasner and Rocco A. Servedio 
Vol 5, Article 8 (pp 141172)
Parallel Repetition: Simplification and the NoSignaling Case by Thomas Holenstein 
Vol 5, Article 7 (pp 135140)
[NOTE]
A Simple Proof of Toda's Theorem by Lance Fortnow 
Vol 5, Article 3 (pp 6982)
Unconditional Pseudorandom Generators for Low Degree Polynomials by Shachar Lovett 
Vol 5, Article 1 (pp 142)
The Power of Unentanglement by Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor 
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 5 (pp 111128)
Approximation Algorithms for Unique Games by Luca Trevisan 
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 11 (pp 211219)
The Randomized Communication Complexity of Set Disjointness by Johan Håstad and Avi Wigderson 
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 3, Article 4 (pp 6179)
A Simple PromiseBQPcomplete Matrix Problem by Dominik Janzing and Pawel Wocjan 
Vol 3, Article 3 (pp 4560)
On the Hardness of Satisfiability with Bounded Occurrences in the PolynomialTime Hierarchy by Ishay Haviv, Oded Regev, and Amnon TaShma 
Vol 3, Article 2 (pp 2543)
Easily refutable subformulas of large random 3CNF formulas by Uriel Feige and Eran Ofek 
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 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 7 (pp 119148)
Query Efficient PCPs with Perfect Completeness by Johan Håstad and Subhash Khot 
Vol 1, Article 5 (pp 81103)
Quantum Fanout is Powerful by Peter Høyer and Robert Špalek 
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 
Vol 1, Article 1 (pp 128)
Limitations of Quantum Advice and OneWay Communication by Scott Aaronson 