Articles under category:<br>Complexity Theory: Theory of Computing: An Open Access Electronic Journal in Theoretical Computer Science

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?
by Clément L. Canonne

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 20, Article 7 (pp 1-62)
Lower Bound Techniques in the Comparison-Query Model and Applications to Inversion Minimization
by Ivan Hu, Dieter van Melkebeek, and Andrew Morgan

Vol 19, Article 9 (pp 1-35)
Optimal Composition Theorem for Randomized Query Complexity
by Dmytro Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal

Vol 19, Article 4 (pp 1-61) [CCC20 Spec Issue]
Non-Disjoint Promise Problems from Meta-Computational View of Pseudorandom Generator Constructions
by Shuichi Hirahara

Vol 19, Article 3 (pp 1-56)
Exponentially Small Soundness for the Direct Product Z-test
by Irit Dinur and Inbal Livni Navon

Vol 18, Article 22 (pp 1-22)
The (Generalized) Orthogonality Dimension of (Generalized) Kneser Graphs: Bounds and Applications
by Alexander Golovnev and Ishay Haviv

Vol 18, Article 21 (pp 1-32) [CCC20 Spec Issue]
Hitting Sets Give Two-Sided Derandomization of Small Space
by Kuan Cheng and William M. Hoza

Vol 18, Article 19 (pp 1-22) [CCC20 Spec Issue]
Sign-Rank vs. Discrepancy
by Kaave Hosseini, Hamed Hatami, and Shachar Lovett

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
by Alexander Kozachinskiy and Vladimir V. Podolskii

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
by Lukas Fleischer

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
by Michael A. Forbes, Amir Shpilka, Iddo Tzameret, and Avi Wigderson

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
by Dmitry Gavinsky

Vol 17, Article 6 (pp 1-57)
Almost Polynomial Hardness of Node-Disjoint Paths in Grids
by Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat

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 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
by Yuval Filmus

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
by Pavel Hrubeš

Vol 16, Article 8 (pp 1-55)
Inaccessible Entropy II: IE Functions and Universal One-Way Hashing
by Iftach Haitner, Thomas Holenstein, Omer Reingold, Salil Vadhan, and Hoeteck Wee

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 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
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 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
by Swagato Sanyal

Vol 15, Article 10 (pp 1-26) [CCC18 Spec Issue]
Pseudorandom Generators from Polarizing Random Walks
by Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett

Vol 15, Article 9 (pp 1-3) [CCC18 Spec Issue]
Special Issue: CCC 2018: Guest Editor's Foreword
by Srikanth Srinivasan

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
by Vikraman Arvind, Pushkar S. Joglekar, Partha Mukhopadhyay, and S. Raja

Vol 15, Article 2 (pp 1-31)
Time Bounds for Streaming Problems
by Raphaël Clifford, Markus Jalsenius, and Benjamin Sach

Vol 15, Article 1 (pp 1-55)
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 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 13 (pp 1-17)
On the Hardness of Learning With Errors with Binary Secrets
by Daniele Micciancio

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 11 (pp 1-37)
How to Verify a Quantum Computation
by Anne Broadbent

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 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
by F. Bruce Shepherd and Adrian R. Vetta

Vol 13, Article 18 (pp 1-15)
Monotone Projection Lower Bounds from Extended Formulation Lower Bounds
by Joshua A. Grochow

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
by Hervé Fournier, Nutan Limaye, Meena Mahajan, and Srikanth Srinivasan

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
by Cody D. Murray and R. Ryan Williams

Vol 13, Article 3 (pp 1-24) [APRX-RND15 Spec Issue]
Towards a Characterization of Approximation Resistance for Symmetric CSPs
by Venkatesan Guruswami and Euiwoong Lee

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
by Prahladh Harsha

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
by Nutan Limaye, Guillaume Malod, and Srikanth Srinivasan

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
by Amit Chakrabarti, Graham Cormode, and Andrew McGregor

Vol 12, Article 6 (pp 1-11) [NOTE]
Simple Proof of Hardness of Feedback Vertex Set
by Venkatesan Guruswami and Euiwoong Lee

Vol 12, Article 5 (pp 1-14)
A Tradeoff Between Length and Width in Resolution
by Neil Thapen

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
by Matthew McKague

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
by Jacek Jendrej, Krzysztof Oleszkiewicz, and Jakub O. Wojtaszczyk

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 11, Article 10 (pp 257-283) [APRX-RND13 Spec Issue]
On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems
by Per Austrin, Rajsekar Manokaran, and Cenny Wenner

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
by Dana Moshkovitz

Vol 11, Article 6 (pp 183-219)
How Hard Is It to Approximate the Jones Polynomial?
by Greg Kuperberg

Vol 11, Article 3 (pp 59-103)
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 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
by Thomas Watson

Vol 10, Article 19 (pp 515-533)
Query Complexity Lower Bounds for Reconstruction of Codes
by Sourav Chakraborty, Eldar Fischer, and Arie Matsliah

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
by Deeparnab Chakrabarty and C. Seshadhri

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 12 (pp 297-339)
Width-Parametrized SAT: Time--Space Tradeoffs
by Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, and Bangsheng Tang

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 Ω(n^1/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

Articles under category:Complexity Theory: Theory of Computing: An Open Access Electronic Journal in Theoretical Computer Science

Articles under category:
Complexity Theory: Theory of Computing: An Open Access Electronic Journal in Theoretical Computer Science