Computational Complexity, Volume 15

Volume 15, Number 1, May 2006

• Kiran S. Kedlaya:
  Quantum computation of zeta functions of curves. 1-19
  
• Elad Hazan, Shmuel Safra, Oded Schwartz:
  On the complexity of approximating k-set packing. 20-39
  
• Jan Kára, Daniel Král:
  Free binary decision diagrams for the computation of EAR_n. 40-61
  
• Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay:
  Circuits on cylinders. 62-81
  
• Richard Beigel, Lance Fortnow, William I. Gasarch:
  A tight lower bound for restricted pir protocols. 82-91
  

Volume 15, Number 2, June 2006

• Anna Gál:
  Special Issue "Conference on Computational Complexity 2005" Guest Editor's Foreword. 93
  
• Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar:
  On the Hardness of Approximating Multicut and Sparsest-Cut. 94-114
  
• Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
  Computationally Private Randomizing Polynomials and Their Applications. 115-162
  
• Sophie Laplante, Troy Lee, Mario Szegedy:
  The Quantum Adversary Method and Classical Formula Size Lower Bounds. 163-196
  

Volume 15, Number 3, October 2006

• Peter Bürgisser, Felipe Cucker, Paulin Jacobé de Naurois:
  The complexity of semilinear problems in succinct representation. 197-235
  
• Saugata Basu:
  Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities. 236-251
  
• Nader H. Bshouty, Michael Kaminski:
  Polynomial multiplication over finite fields: from quadratic to straight-line complexity. 252-262
  
• Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan:
  Lower bounds for linear locally decodable codes and private information retrieval. 263-296
  

Volume 15, Number 4, December 2006

• Anna Gál:
  Special Issue "Conference on Computational Complexity 2005" Guest Editor's Foreword. 297
  
• Ronen Shaltiel, Christopher Umans:
  Pseudorandomness for Approximate Counting and Sampling. 298-341
  
• Neeraj Kayal, Nitin Saxena:
  Complexity of Ring Morphism Problems. 342-390
  
• Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson:
  A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness. 391-432
  
• Ryan Williams:
  Inductive Time-Space Lower Bounds for Sat and Related Problems. 433-470