- Open Access
PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz and Shmuel Safra
2011, Volume 20, Number 3, Pages 413-504
- Open Access
Derandomized Parallel Repetition via Structured PCPs
Irit Dinur and Or Meir
2011, Volume 20, Number 2, Pages 207-327
- Open Access
Special Issue On Worst-case Versus Average-case Complexity Editors’ Foreword
Oded Goldreich and Salil Vadhan
2007, Volume 16, Number 4, Pages 325-330
- Open Access
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions
Daniele Micciancio
2007, Volume 16, Number 4, Pages 365-411
- Open Access
Pseudorandomness and Average-Case Complexity Via Uniform Reductions
Luca Trevisan and Salil Vadhan
2007, Volume 16, Number 4, Pages 331-364
- Open Access
If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances
Dan Gutfreund, Ronen Shaltiel and Amnon Ta-Shma
2007, Volume 16, Number 4, Pages 412-441
- Open Access
Polynomial Identity Testing for Depth 3 Circuits
Neeraj Kayal and Nitin Saxena
2007, Volume 16, Number 2, Pages 115-138
- Open Access
Special Issue “Conference on Computational Complexity 2006” Guest Editors’ Foreword
Venkatesan Guruswami and Valentine Kabanets
2007, Volume 16, Number 2, Pages 113-114
- Open Access
A Generic Time Hierarchy with One Bit of Advice
Dieter van Melkebeek and Konstantin Pervyshev
2007, Volume 16, Number 2, Pages 139-179
- Open Access
Every Linear Threshold Function has a Low-Weight Approximator
Rocco A. Servedio
2007, Volume 16, Number 2, Pages 180-209