Computational Complexity, Volume 18

Volume 18, Number 1, April 2009

• Zeev Dvir, Ariel Gabizon, Avi Wigderson:
  Extractors And Rank Extractors For Polynomial Sources. 1-58
  
• Ali Juma, Valentine Kabanets, Charles Rackoff, Amir Shpilka:
  The Black-Box Query Complexity of Polynomial Summation. 59-79
  
• Peter Bürgisser:
  On Defining Integers And Proving Arithmetic Circuit Lower Bounds. 81-103
  
• Ezequiel Dratman, Guillermo Matera, Ariel Waissbein:
  Robust Algorithms For Generalized Pham Systems. 105-154
  
• Amir Hashemi:
  Nullstellensätze for Zero-Dimensional Gröbner Bases. 155-168
  

Volume 18, Number 2, June 2009

• Paul Beame, Amit Chakrabarti:
  Special Issue "Conference on Computational Complexity 2008" Guest Editors' Foreword. 169-170
  
• Ran Raz, Amir Yehudayoff:
  Lower Bounds and Separations for Constant Depth Multilinear Circuits. 171-207
  
• Emanuele Viola:
  The Sum of D Small-Bias Generators Fools Polynomials of Degree D. 209-217
  
• Alexander A. Sherstov:
  Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. 219-247
  
• Per Austrin, Elchanan Mossel:
  Approximation Resistant Predicates from Pairwise Independence. 249-271
  
• Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick:
  Using Entanglement in Quantum Multi-Prover Interactive Proofs. 273-307
  
• Troy Lee, Adi Shraibman:
  Disjointness is Hard in the Multiparty Number-on-the-Forehead Model. 309-336