Articles under category:
Complexity Theory
Complexity Theory
|
Volume 7, Article 13 (pages 185-188)
[NOTE]
Computing Polynomials with Few Multiplications by Shachar Lovett |
|
Volume 7, Article 12 (pages 177-184)
[NOTE]
On Circuit Lower Bounds from Derandomization by Scott Aaronson and Dieter van Melkebeek |
|
Volume 7, Article 11 (pages 155-176)
Distribution-Free Testing for Monomials with a Sublinear Number of Queries by Elya Dolev and Dana Ron |
|
Volume 7, Article 10 (pages 147-153)
[NOTE]
The Influence Lower Bound Via Query Elimination by Rahul Jain and Shengyu Zhang |
|
Volume 7, Article 7 (pages 101-117)
Quantum Interactive Proofs with Short Messages by Salman Beigi, Peter Shor, and John Watrous |
|
Volume 7, Article 6 (pages 75-99)
Testing Linear-Invariant Non-Linear Properties by Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie |
|
Volume 7, Article 4 (pages 45-48)
[NOTE]
Tight Bounds on the Average Sensitivity of k-CNF by Kazuyuki Amano |
|
Volume 6, Article 10 (pages 227-245)
A Separation of NP and coNP in Multiparty Communication Complexity by Dmitry Gavinsky and Alexander A. Sherstov |
|
Volume 6, Article 9 (pages 201-225)
Separating Deterministic from Randomized Multiparty Communication Complexity by Paul Beame, Matei David, Toniann Pitassi, and Philipp Woelfel |
|
Volume 6, Article 7 (pages 135-177)
Elusive Functions and Lower Bounds for Arithmetic Circuits by Ran Raz |
|
Volume 6, Article 6 (pages 113-134)
Rounds vs. Queries Tradeoff in Noisy Computation by Navin Goyal and Michael Saks |
|
Volume 6, Article 4 (pages 81-84)
[NOTE]
Decision Trees and Influence: an Inductive Proof of the OSSS Inequality by Homin K. Lee |
|
Volume 6, Article 1 (pages 1-25)
A New Quantum Lower Bound Method, with an Application to a Strong Direct Product Theorem for Quantum Search by Andris Ambainis |
|
Volume 5, Article 13 (pages 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 |
|
Volume 5, Article 10 (pages 191-216)
Distribution-Free Testing Lower Bound for Basic Boolean Functions by Dana Glasner and Rocco A. Servedio |
|
Volume 5, Article 8 (pages 141-172)
Parallel Repetition: Simplification and the No-Signaling Case by Thomas Holenstein |
|
Volume 5, Article 7 (pages 135-140)
[NOTE]
A Simple Proof of Toda's Theorem by Lance Fortnow |
|
Volume 5, Article 3 (pages 69-82)
Unconditional Pseudorandom Generators for Low Degree Polynomials by Shachar Lovett |
|
Volume 5, Article 1 (pages 1-42)
The Power of Unentanglement by Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor |
|
Volume 4, Article 7 (pages 137-168)
Norms, XOR Lemmas, and Lower Bounds for Polynomials and Protocols by Emanuele Viola and Avi Wigderson |
|
Volume 4, Article 6 (pages 129-135)
The One-Way Communication Complexity of Hamming Distance by T. S. Jayram, Ravi Kumar, and D. Sivakumar |
|
Volume 4, Article 5 (pages 111-128)
Approximation Algorithms for Unique Games by Luca Trevisan |
|
Volume 3, Article 12 (pages 221-238)
An Ω(n1/3) Lower Bound for Bilinear Group Based Private Information Retrieval by Alexander Razborov and Sergey Yekhanin |
|
Volume 3, Article 11 (pages 211-219)
The Randomized Communication Complexity of Set Disjointness by Johan Håstad and Avi Wigderson |
|
Volume 3, Article 7 (pages 129-157)
Quantum Versus Classical Proofs and Advice by Scott Aaronson and Greg Kuperberg |
|
Volume 3, Article 5 (pages 81-102)
An Exponential Separation between Regular and General Resolution by Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, and Alasdair Urquhart |
|
Volume 3, Article 4 (pages 61-79)
A Simple PromiseBQP-complete Matrix Problem by Dominik Janzing and Pawel Wocjan |
|
Volume 3, Article 3 (pages 45-60)
On the Hardness of Satisfiability with Bounded Occurrences in the Polynomial-Time Hierarchy by Ishay Haviv, Oded Regev, and Amnon Ta-Shma |
|
Volume 3, Article 2 (pages 25-43)
Easily refutable subformulas of large random 3CNF formulas by Uriel Feige and Eran Ofek |
|
Volume 2, Article 9 (pages 173-183)
Tolerant Versus Intolerant Testing for Boolean Properties by Eldar Fischer and Lance Fortnow |
|
Volume 2, Article 6 (pages 121-135)
Separation of Multilinear Circuit and Formula Size by Ran Raz |
|
Volume 2, Article 4 (pages 65-90)
Rank Bounds and Integrality Gaps for Cutting Planes Procedures by Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, and Toniann Pitassi |
|
Volume 1, Article 9 (pages 177-216)
Linear Equations, Arithmetic Progressions and Hypergraph Property Testing by Noga Alon and Asaf Shapira |
|
Volume 1, Article 8 (pages 149-176)
A Non-linear Time Lower Bound for Boolean Branching Programs by Miklós Ajtai |
|
Volume 1, Article 7 (pages 119-148)
Query Efficient PCPs with Perfect Completeness by Johan Håstad and Subhash Khot |
|
Volume 1, Article 5 (pages 81-103)
Quantum Fan-out is Powerful by Peter Høyer and Robert Špalek |
|
Volume 1, Article 4 (pages 47-79)
Quantum Search of Spatial Regions by Scott Aaronson and Andris Ambainis |
|
Volume 1, Article 3 (pages 37-46)
Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range by Andris Ambainis |
|
Volume 1, Article 2 (pages 29-36)
Quantum Lower Bound for the Collision Problem with Small Range by Samuel Kutin |
|
Volume 1, Article 1 (pages 1-28)
Limitations of Quantum Advice and One-Way Communication by Scott Aaronson |
|
ToC Library Graduate Surveys 4 (2011) 27 pages
Variations on the Sensitivity Conjecture by Pooya Hatami, Raghav Kulkarni, and Denis Pankratov |