Computational Complexity, Volume 21

Volume 21, Number 1, March 2012

• Oded Goldreich, Salil P. Vadhan:
  Special issue from RANDOM'09: Editors' Foreword. 1
  
• Jeff Kinne, Dieter van Melkebeek, Ronen Shaltiel:
  Pseudorandom Generators, Typically-Correct Derandomization, and Circuit Lower Bounds. 3-61
  
• Ido Ben-Eliezer, Rani Hod, Shachar Lovett:
  Random low-degree polynomials are hard to approximate. 63-81
  
• Andrej Bogdanov, Youming Qiao:
  On the security of Goldreich's one-way function. 83-127
  
• Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg:
  Hierarchy Theorems for Property Testing. 129-192
  

Volume 21, Number 2, June 2012

• Anup Rao:
  Special Issue "Conference on Computational Complexity 2011" Guest Editor's Foreword. 193-195
  
• Andrew Drucker:
  Improved direct product theorems for randomized query complexity. 197-244
  
• Shachar Lovett, Emanuele Viola:
  Bounded-Depth Circuits Cannot Sample Good Codes. 245-266
  
• Eli Ben-Sasson, Michael Viderman:
  Towards lower bounds on locally testable codes via density arguments. 267-309
  
• Eric Blais, Joshua Brody, Kevin Matulef:
  Property Testing Lower Bounds via Communication Complexity. 311-358
  

Volume 21, Number 3, September 2012

• Markus Bläser, Holger Dell, Mahmoud Fouz:
  Complexity and Approximability of the Cover Polynomial. 359-419
  
• Jacek Pomykala, Bartosz Zralek:
  On reducing factorization to the discrete logarithm problem modulo a composite. 421-429
  
• Henning Wunderlich:
  On a Theorem of Razborov. 431-477
  
• Luis Filipe Coelho Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto:
  Low-Depth Witnesses are Easy to Find. 479-497
  
• Hugue Blier, Alain Tapp:
  A Quantum Characterization Of NP. 499-510
  
• Hannah Alpert, Jennifer Iglesias:
  Length 3 Edge-Disjoint Paths Is NP-Hard. 511-513
  

Volume 21, Number 4, December 2012

• Zeev Dvir:
  Extractors for varieties. 515-572
  
• Jin-Yi Cai, Pinyan Lu, Mingji Xia:
  Holographic reduction, interpolation and hardness. 573-604
  
• Leslie Ann Goldberg, Mark Jerrum:
  Inapproximability of the Tutte polynomial of a planar graph. 605-642
  
• Aduri Pavan, Raghunath Tewari, N. V. Vinodchandran:
  On the power of unambiguity in log-space. 643-670
  

Last update Sat May 25 19:45:19 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page