Volume 7 (2011)
Vol 7, Article 1 (pp 1-18)
Noisy Interpolating Sets for Low-Degree Polynomials
by Zeev Dvir and Amir Shpilka
Vol 7, Article 2 (pp 19-25) [NOTE]
Inverting a Permutation is as Hard as Unordered Search
by Ashwin Nayak
Vol 7, Article 3 (pp 27-43)
Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs
by Per Austrin, Subhash Khot, and Muli Safra
Vol 7, Article 4 (pp 45-48) [NOTE]
Tight Bounds on the Average Sensitivity of k-CNF
by Kazuyuki Amano
Vol 7, Article 5 (pp 49-74)
Metric Clustering via Consistent Labeling
by Robert Krauthgamer and Tim Roughgarden
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 7 (pp 101-117)
Quantum Interactive Proofs with Short Messages
by Salman Beigi, Peter Shor, and John Watrous
Vol 7, Article 8 (pp 119-129)
Arithmetic Complexity in Ring Extensions
by Pavel Hrubeš and Amir Yehudayoff
Vol 7, Article 9 (pp 131-145)
Inverse Conjecture for the Gowers Norm is False
by Shachar Lovett, Roy Meshulam, and Alex Samorodnitsky
Vol 7, Article 10 (pp 147-153) [NOTE]
The Influence Lower Bound Via Query Elimination
by Rahul Jain and Shengyu Zhang
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 12 (pp 177-184) [NOTE]
On Circuit Lower Bounds from Derandomization
by Scott Aaronson and Dieter van Melkebeek
Vol 7, Article 13 (pp 185-188) [NOTE]
Computing Polynomials with Few Multiplications
by Shachar Lovett
List of Editors