Computational Complexity, Volume 14

Volume 14, Number 1, April 2005

• Ran Raz, Amir Shpilka:
  Deterministic polynomial identity testing in non-commutative models. 1-19
  
• Dima Grigoriev, Dmitrii V. Pasechnik:
  Polynomial-time computing over quadratic maps i: sampling in real algebraic sets. 20-52
  
• Saugata Basu, Richard Pollack, Marie-Françoise Roy:
  Computing the euler-poincaré characteristics of sign conditions. 53-71
  
• Lars Kristiansen:
  Neat function algebraic characterizations of logspace and linspace. 72-88
  

Volume 14, Number 2, June 2005

• Eric Allender:
  Special issue "Conference on Computational Complexity 2004" Guest Editor's foreword. 89
  
• Venkatesan Guruswami, Daniele Micciancio, Oded Regev:
  The complexity of the covering radius problem. 90-121
  
• Chris Marriott, John Watrous:
  Quantum Arthur-Merlin games. 122-152
  
• Dániel Marx:
  Parameterized complexity of constraint satisfaction problems. 153-183
  

Volume 14, Number 3, December 2005

• Eric Allender:
  Special issue, final part "Conference on Computational Complexity 2004 " Guest Editor's foreword. 185
  
• Luca Trevisan, Salil P. Vadhan, David Zuckerman:
  Compression of Samplable Sources. 186-227
  
• Harry Buhrman, Troy Lee, Dieter van Melkebeek:
  Language compression and pseudorandom generators. 228-255
  
• Peter Bro Miltersen, N. V. Vinodchandran:
  Derandomizing Arthur-Merlin Games using Hitting Sets. 256-279
  

Volume 14, Number 4, March 2006

• Shmuel Safra, Oded Schwartz:
  On the complexity of approximating tsp with neighborhoods and related problems. 281-307
  
• Dániel Marx:
  The complexity of chromatic strength and chromatic edge strength. 308-340
  
• Chris Pollett:
  Languages to diagonalize against advice classes. 341-361
  
• Matthias Krause:
  On the computational power of Boolean decision lists. 362-375