Computational Complexity, Volume 17

Volume 17, Number 1, April 2008

• Oded Goldreich:
  Preface to the Special Issue from Random'06. 1-2
  
• Alexander Healy:
  Randomness-Efficient Sampling within NC¹. 3-37
  
• Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
  On Pseudorandom Generators with Linear Stretch in NC⁰. 38-69
  
• Oded Lachish, Ilan Newman, Asaf Shapira:
  Space Complexity Vs. Query Complexity. 70-93
  
• Hubie Chen:
  Inverse NP Problems. 94-118
  
• John M. Hitchcock, Aduri Pavan:
  Hardness Hypotheses, Derandomization, and Circuit Complexity. 119-146
  

Volume 17, Number 2, May 2008

• Peter Bro Miltersen:
  Special Issue: "Conference on Computational Complexity 2007" Guest Editor's Foreword. 147-148
  
• Alexander A. Sherstov:
  Halfspace Matrices. 149-178
  
• R. Ryan Williams:
  Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. 179-219
  
• Marius Zimand:
  Exposure-Resilient Extractors and the Derandomization of Probabilistic Sublinear Time. 220-253
  
• Jin-yi Cai, Pinyan Lu:
  Basis Collapse in Holographic Algorithms. 254-281
  
• Richard Cleve, William Slofstra, Falk Unger, Sarvagya Upadhyay:
  Perfect Parallel Repetition Theorem for Quantum Xor Proof Systems. 282-299
  
• Chris Peikert:
  Limits on the Hardness of Lattice Problems in l_p Norms. 300-351
  

Volume 17, Number 3, October 2008

• Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans:
  On the Complexity of Succinct Zero-Sum Games. 353-376
  
• Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton:
  Polynomials that Sign Represent Parity and Descartes' Rule of Signs. 377-406
  
• Ran Raz, Iddo Tzameret:
  The Strength of Multilinear Proofs. 407-457
  

Volume 17, Number 4, December 2008

• Xiaoyang Gu, Jack H. Lutz:
  Dimension Characterizations of Complexity Classes. 459-474
  
• Venkatesan Guruswami, Valentine Kabanets:
  Hardness Amplification via Space-Efficient Direct Products. 475-500
  
• Aduri Pavan, N. V. Vinodchandran:
  2-Local Random Reductions to 3-Valued Functions. 501-514
  
• Ran Raz, Amir Yehudayoff:
  Balancing Syntactically Multilinear Arithmetic Circuits. 515-535
  
• Dima Grigoriev:
  Probabilistic Communication Complexity Over The Reals. 536-548
  
• Johan Håstad:
  Every 2-csp Allows Nontrivial Approximation. 549-566