Computational Complexity, Volume 17

Volume 17, Number 1, April 2008

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

Volume 17, Number 2, May 2008

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

Volume 17, Number 3, October 2008

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