Articles under category:
Note
Vol 9, Article 29 (pp 889-896) [NOTE] [Boolean Spec Issue]
Hypercontractivity Via the Entropy Method
by Eric Blais and Li-Yang Tan
Vol 9, Article 17 (pp 587-592) [NOTE] [Boolean Spec Issue]
A Monotone Function Given By a Low-Depth Decision Tree That Is Not an Approximate Junta
by Daniel Kane
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 8, Article 16 (pp 369-374) [NOTE]
Quantum Private Information Retrieval with Sublinear Communication Complexity
by François Le Gall
Vol 8, Article 10 (pp 231-238) [NOTE]
Monotone Circuits: One-Way Functions versus Pseudorandom Generators
by Oded Goldreich and Rani Izsak
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 10 (pp 147-153) [NOTE]
The Influence Lower Bound Via Query Elimination
by Rahul Jain and Shengyu Zhang
Vol 7, Article 4 (pp 45-48) [NOTE]
Tight Bounds on the Average Sensitivity of k-CNF
by Kazuyuki Amano
Vol 7, Article 2 (pp 19-25) [NOTE]
Inverting a Permutation is as Hard as Unordered Search
by Ashwin Nayak
Vol 6, Article 4 (pp 81-84) [NOTE]
Decision Trees and Influence: an Inductive Proof of the OSSS Inequality
by Homin K. Lee
Vol 5, Article 7 (pp 135-140) [NOTE]
A Simple Proof of Toda's Theorem
by Lance Fortnow
Vol 5, Article 5 (pp 119-123) [NOTE]
Discrete-Query Quantum Algorithm for NAND Trees
by Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo