Volume 20, Number 1, March 2011

• 
  Pascal Koiran, Sylvain Perifel: Interpolation in Valiant's Theory. 1-20
• 
  Mark Kambites: Generic Complexity of Finitely Presented Monoids and Semigroups. 21-50
• 
  Stefan S. Dantchev, Barnaby Martin, Stefan Szeider: Parameterized Proof Complexity. 51-85
• 
  Ronen Shaltiel: Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma. 87-143
• 
  Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu: Complexity of Hard-Core Set Proofs. 145-171

Volume 20, Number 2, June 2011

Selected papers from the 25th Annual IEEE Conference on Computational Complexity (CCC 2010)

• 
  Dieter van Melkebeek: Special Issue "Conference on Computational Complexity 2010" Guest Editor's Foreword. 173-175
• 
  Alexandra Kolla: Spectral Algorithms for Unique Games. 177-206
• 
  Irit Dinur, Or Meir: Derandomized Parallel Repetition via Structured PCPs. 207-327
• 
  Baris Aydinlioglu, Dan Gutfreund, John M. Hitchcock, Akinori Kawachi: Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds. 329-366
• 
  Zeev Dvir: On Matrix Rigidity and Locally Self-correctable Codes. 367-388
• 
  Daniel M. Kane: The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions. 389-412

Volume 20, Number 3, September 2011

• 
  Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra: PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability. 413-504
• 
  Venkatesan T. Chakaravarthy, Sambuddha Roy: Arthur and Merlin as Oracles. 505-558
• 
  Pavel Hrubes, Amir Yehudayoff: Homogeneous Formulas and Symmetric Polynomials. 559-578

Volume 20, Number 4, December 2011

Special issue in memory of Misha Alekhnovich

• 
  Allan Borodin, Toniann Pitassi, Alexander A. Razborov: Special Issue In Memory of Misha Alekhnovich. Foreword. 579-590
• 
  Max Nalsky, Michael Ostrovsky: Obituary. 591-595
• 
  Michael Alekhnovich: Lower Bounds for k-DNF Resolution on Random 3-CNFs. 597-614
• 
  Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis: Towards Strong Nonapproximability Results in the Lovász-Schrijver Hierarchy. 615-648
• 
  Michael Alekhnovich, Alexander A. Razborov: Satisfiability, Branch-Width and Tseitin tautologies. 649-678
• 
  Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi: Toward a Model for Backtracking and Dynamic Programming. 679-740
• 
  Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi: Hardness of Approximating the Closest Vector Problem with Pre-Processing. 741-753
• 
  Michael Alekhnovich: More on Average Case vs Approximation Complexity. 755-786