List of accepted papers for CCC 2009: Parallel approximation of non-interactive zero-sum quantum games Rahul Jain and John Watrous Infinite vs. Finite Space-Bounded Randomized Computations Richard Kralovic Extractors for varieties Zeev Dvir An Almost Optimal Rank Bound for Depth-3 Identities Nitin Saxena and C. Seshadri Extractors for Low-Weight Affine Sources Anup Rao The complexity of the annihilating polynomial Neeraj Kayal A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent Pascal Koiran and Sylvain Perifel Increasing the gap between Descriptional Complexity and Algorithmic Probability Adam R. Day One-Way Functions and the Isomorphism Conjecture Manindra Agrawal and Osamu Watanabe Lower bounds on the randomized communication complexity of read-once functions Nikos Leonardos and Michael Saks k-Subgraph Isomorphism on AC0 Circuits Kazuyuki Amano Planar Graph Isomorphism is in Log-Space Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, and Fabian Wagner Locally Testable Codes Require Redundant Testers Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, and Michael Viderman Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in Zohar S. Karnin and Amir Shpilka A new characterization of ACC0 and probabilistic CC0. Kristoffer Arnsfelt Hansen and Michal Kouck? On basing ZK ? BPP on the hardness of PAC learning David Xiao Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies Tsuyoshi Ito, Hirotada Kobayashi, and Keiji Matsumoto Poly-logarithmic independence fools AC0 circuits Mark Braverman Improved Approximation of Linear Threshold Functions Ilias Diakonikolas and Rocco A. Servedio A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences Joshua Brody and Amit Chakrabarti Weak derandomization of weak algorithms: explicit versions of Yao's lemma Ronen Shaltiel Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs Per Austrin, Subhash Khot, and Muli Safra Every Permutation CSP of arity 3 is Approximation Resistant Moses Charikar, Venkatesan Guruswami, and Rajsekar Manokaran New Results in the Simultaneous Message Passing Model Rahul Jain and Hartmut Klauck Communication Complexity of Read Once AC0 Formulae T.S. Jayram, Swastik Kopparty, and Prasad Raghavendra The Maximum Communication Complexity of Multi-party Pointer Jumping Joshua Brody Worst-Case Running Times for Average-Case Algorithms Luis Antunes and Lance Fortnow Lipschitz continuous ordinary differential equations are polynomial-space complete Akitoshi Kawamura Quantum Copy-Protection and Quantum Money Scott Aaronson The Proof Complexity of Polynomial Identities Pavel Hrubes and Iddo Tzameret An approximation algorithm for approximation rank Troy Lee and Adi Shraibman Lower bounds on quantum multiparty communication complexity Troy Lee, Gideon Schechtman, and Adi Shraibman Fixed-Polynomial Size Circuit Bounds Lance Fortnow, Rahul Santhanam, and Ryan Williams On the degree of Boolean functions in different characteristics Parikshit Gopalan, Shachar Lovett, and Amir Shpilka Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution Luca Trevisan, Madhur Tulsiani, and Salil Vadhan Are PCPs Inherent in Efficient Arguments Guy Rothblum and Salil Vadhan Multitask Efficiencies in the Decision Tree Model Andrew Drucker