CCC 2009: Accepted papers

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 AC₀ 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 ACC⁰ and probabilistic CC⁰.
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 AC₀ 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 AC₀ 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