Volume 7, Number 1, 2011

• 
  Zeev Dvir, Amir Shpilka: Noisy Interpolating Sets for Low-Degree Polynomials. 1-18
• 
  Ashwin Nayak: Inverting a Permutation is as Hard as Unordered Search. 19-25
• 
  Per Austrin, Subhash Khot, Muli Safra: Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. 27-43
• 
  Kazuyuki Amano: Tight Bounds on the Average Sensitivity of k-CNF. 45-48
• 
  Robert Krauthgamer, Tim Roughgarden: Metric Clustering via Consistent Labeling. 49-74
• 
  Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie: Testing Linear-Invariant Non-Linear Properties. 75-99
• 
  Salman Beigi, Peter W. Shor, John Watrous: Quantum Interactive Proofs with Short Messages. 101-117
• 
  Pavel Hrubes, Amir Yehudayoff: Arithmetic Complexity in Ring Extensions. 119-129
• 
  Shachar Lovett, Roy Meshulam, Alex Samorodnitsky: Inverse Conjecture for the Gowers Norm is False. 131-145
• 
  Rahul Jain, Shengyu Zhang: The Influence Lower Bound Via Query Elimination. 147-153
• 
  Elya Dolev, Dana Ron: Distribution-Free Testing for Monomials with a Sublinear Number of Queries. 155-176
• 
  Scott Aaronson, Dieter van Melkebeek: On Circuit Lower Bounds from Derandomization. 177-184
• 
  Shachar Lovett: Computing Polynomials with Few Multiplications. 185-188

last updated on Sun May 26 03:24:12 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page