| 2009 | A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences. Joshua Brody, Amit Chakrabarti |
| 2009 | A New Characterization of ACC Kristoffer Arnsfelt Hansen, Michal Koucký |
| 2009 | A Superpolynomial Lower Bound on the Size of Uniform Non-constant-depth Threshold Circuits for the Permanent. Pascal Koiran, Sylvain Perifel |
| 2009 | An Almost Optimal Rank Bound for Depth-3 Identities. Nitin Saxena, C. Seshadhri |
| 2009 | An Approximation Algorithm for Approximation Rank. Troy Lee, Adi Shraibman |
| 2009 | Are PCPs Inherent in Efficient Arguments? Guy N. Rothblum, Salil P. Vadhan |
| 2009 | Every Permutation CSP of arity 3 is Approximation Resistant. Moses Charikar, Venkatesan Guruswami, Rajsekar Manokaran |
| 2009 | Extractors for Low-Weight Affine Sources. Anup Rao |
| 2009 | Extractors for Varieties. Zeev Dvir |
| 2009 | Fixed-Polynomial Size Circuit Bounds. Lance Fortnow, Rahul Santhanam, Ryan Williams |
| 2009 | Improved Approximation of Linear Threshold Functions. Ilias Diakonikolas, Rocco A. Servedio |
| 2009 | Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs. Per Austrin, Subhash Khot, Muli Safra |
| 2009 | Increasing the Gap between Descriptional Complexity and Algorithmic Probability. Adam R. Day |
| 2009 | Infinite vs. Finite Space-Bounded Randomized Computations. Richard Královic |
| 2009 | Lipschitz Continuous Ordinary Differential Equations are Polynomial-Space Complete. Akitoshi Kawamura |
| 2009 | Locally Testable Codes Require Redundant Testers. Eli Ben-Sasson, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan, Michael Viderman |
| 2009 | Lower Bounds on Quantum Multiparty Communication Complexity. Troy Lee, Gideon Schechtman, Adi Shraibman |
| 2009 | Lower Bounds on the Randomized Communication Complexity of Read-Once Functions. Nikos Leonardos, Michael E. Saks |
| 2009 | Multitask Efficiencies in the Decision Tree Model. Andrew Drucker |
| 2009 | New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques. Rahul Jain, Hartmut Klauck |
| 2009 | On Basing ZK ≠ BPP on the Hardness of PAC Learning. David Xiao |
| 2009 | On the Communication Complexity of Read-Once AC^0 Formulae. T. S. Jayram, Swastik Kopparty, Prasad Raghavendra |
| 2009 | On the Complexity of Boolean Functions in Different Characteristics. Parikshit Gopalan, Shachar Lovett, Amir Shpilka |
| 2009 | One-Way Functions and the Berman-Hartmanis Conjecture. Manindra Agrawal, Osamu Watanabe |
| 2009 | Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies. Tsuyoshi Ito, Hirotada Kobayashi, Keiji Matsumoto |
| 2009 | Parallel Approximation of Non-interactive Zero-sum Quantum Games. Rahul Jain, John Watrous |
| 2009 | Planar Graph Isomorphism is in Log-Space. Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner |
| 2009 | Poly-logarithmic Independence Fools AC Mark Braverman |
| 2009 | Proceedings of the 24th Annual IEEE Conference on Computational Complexity, CCC 2009, Paris, France, 15-18 July 2009 |
| 2009 | Quantum Copy-Protection and Quantum Money. Scott Aaronson |
| 2009 | Reconstruction of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in. Zohar Shay Karnin, Amir Shpilka |
| 2009 | Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution. Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan |
| 2009 | The Complexity of the Annihilating Polynomial. Neeraj Kayal |
| 2009 | The Maximum Communication Complexity of Multi-Party Pointer Jumping. Joshua Brody |
| 2009 | The Proof Complexity of Polynomial Identities. Pavel Hrubes, Iddo Tzameret |
| 2009 | Weak Derandomization of Weak Algorithms: Explicit Versions of Yao's Lemma. Ronen Shaltiel |
| 2009 | Worst-Case Running Times for Average-Case Algorithms. Luis Filipe Coelho Antunes, Lance Fortnow |
| 2009 | k-Subgraph Isomorphism on AC Kazuyuki Amano |