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 |