Computational Complexity, Volume 20

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

• 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

• 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
  

Last update Fri May 25 09:00:01 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page