Computational Complexity, Volume 16

Volume 16, Number 1, May 2007

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

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

Oded Goldreich, Salil P. Vadhan:
Special Issue On Worst-case Versus Average-case Complexity Editors' Foreword. 325-330
Electronic Edition (link) BibTeX
Luca Trevisan, Salil P. Vadhan:
Pseudorandomness and Average-Case Complexity Via Uniform Reductions. 331-364
Electronic Edition (link) BibTeX
Daniele Micciancio:
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions. 365-411
Electronic Edition (link) BibTeX
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
Electronic Edition (link) BibTeX