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