| 2007 | 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13-16 June 2007, San Diego, California, USA |
| 2007 | A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover. Grant Schoenebeck, Luca Trevisan, Madhur Tulsiani |
| 2007 | A New Interactive Hashing Theorem. Iftach Haitner, Omer Reingold |
| 2007 | An Exponential Lower Bound on the Size of Constant-Depth Threshold Circuits with Small Energy Complexity. Kei Uchizawa, Eiji Takimoto |
| 2007 | Bases Collapse in Holographic Algorithms. Jin-Yi Cai, Pinyan Lu |
| 2007 | Bounded Queries and the NP Machine Hypothesis. Richard Chang, Suresh Purini |
| 2007 | Directed Planar Reachability is in Unambiguous Log-Space. Chris Bourke, Raghunath Tewari, N. V. Vinodchandran |
| 2007 | Efficient Arguments without Short PCPs. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky |
| 2007 | Halfspace Matrices. Alexander A. Sherstov |
| 2007 | Limits on the Hardness of Lattice Problems in ell _p Norms. Chris Peikert |
| 2007 | Low-Depth Witnesses are Easy to Find. Luis Antunes, Lance Fortnow, Alexandre Pinto, Andre Souto |
| 2007 | Lower Bounds for Multi-Player Pointer Jumping. Amit Chakrabarti |
| 2007 | Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols. Emanuele Viola, Avi Wigderson |
| 2007 | On Approximate Majority and Probabilistic Time. Emanuele Viola |
| 2007 | On C-Degrees, H-Degrees and T-Degrees. Wolfgang Merkle, Frank Stephan |
| 2007 | On Computation and Communication with Small Bias. Harry Buhrman, Nikolai K. Vereshchagin, Ronald de Wolf |
| 2007 | On Derandomizing Probabilistic Sublinear-Time Algorithms. Marius Zimand |
| 2007 | On Heuristic Time Hierarchies. Konstantin Pervyshev |
| 2007 | On Parameterized Path and Chordless Path Problems. Yijia Chen, Jörg Flum |
| 2007 | On the Theory of Matchgate Computations. Jin-Yi Cai, Vinay Choudhary, Pinyan Lu |
| 2007 | Parity Problems in Planar Graphs. Mark Braverman, Raghav Kulkarni, Sambuddha Roy |
| 2007 | Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems. Richard Cleve, William Slofstra, Falk Unger, Sarvagya Upadhyay |
| 2007 | Quantum t-designs: t-wise Independence in the Quantum World. Andris Ambainis, Joseph Emerson |
| 2007 | Quantum versus Classical Proofs and Advice. Scott Aaronson, Greg Kuperberg |
| 2007 | S-T Connectivity on Digraphs with a Known Stationary Distribution. Kai-Min Chung, Omer Reingold, Salil P. Vadhan |
| 2007 | Testing Properties of Constraint-Graphs. Shirley Halevy, Oded Lachish, Ilan Newman, Dekel Tsur |
| 2007 | The Communication Complexity of Correlation. Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan |
| 2007 | The Complexity of Polynomials and Their Coefficient Functions. Guillaume Malod |
| 2007 | Time-Space Tradeoffs for Counting NP Solutions Modulo Integers. Ryan Williams |
| 2007 | Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes. Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan |
| 2007 | Understanding Parallel Repetition Requires Understanding Foams. Uriel Feige, Guy Kindler, Ryan O'Donnell |