Computational Complexity, Volume 16

Volume 16, Number 1, May 2007

• Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, Srinivasan Venkatesh:
  Communication vs. Computation. 1-33
  
• Zeev Dvir, Amir Shpilka:
  An Improved Analysis of Linear Mergers. 34-59
  
• Martin Beaudry, Markus Holzer:
  The Complexity of Tensor Circuit Evaluation. 60-111
  

Volume 16, Number 2, May 2007

• Venkatesan Guruswami, Valentine Kabanets:
  Special Issue "Conference on Computational Complexity 2006" Guest Editors' Foreword. 113-114
  
• Neeraj Kayal, Nitin Saxena:
  Polynomial Identity Testing for Depth 3 Circuits. 115-138
  
• Dieter van Melkebeek, Konstantin Pervyshev:
  A Generic Time Hierarchy with One Bit of Advice. 139-179
  
• Rocco A. Servedio:
  Every Linear Threshold Function has a Low-Weight Approximator. 180-209
  

Volume 16, Number 3, October 2007

• Pierre McKenzie, Klaus W. Wagner:
  The Complexity of Membership Problems for Circuits Over Sets of Natural Numbers. 211-244
  
• Paul Beame, Russell Impagliazzo, Ashish Sabharwal:
  The Resolution Complexity of Independent Sets and Vertex Covers in Random Graphs. 245-297
  
• Ingo Wegener, Philipp Woelfel:
  New Results on the Complexity of the Middle Bit of Multiplication. 298-323
  

Volume 16, Number 4, December 2007

• Oded Goldreich, Salil P. Vadhan:
  Special Issue On Worst-case Versus Average-case Complexity Editors' Foreword. 325-330
  
• Luca Trevisan, Salil P. Vadhan:
  Pseudorandomness and Average-Case Complexity Via Uniform Reductions. 331-364
  
• Daniele Micciancio:
  Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions. 365-411
  
• Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma:
  If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances. 412-441