Accepted papers for CCC '07

A Linear Round Lower Bound for Lovasz-Schrijver SDP Relaxations of Vertex Cover
Grant Schoenebeck, Luca Trevisan, and Madhur Tulsiani

A New Interactive Hashing Theorem
Iftach Haitner and Omer Reingold

An Exponential Lower Bound on the Size of Constant-Depth Threshold Circuits with Small Energy Complexity
Kei Uchizawa and Eiji Takimoto

Bases Collapse in Holographic Algorithms
Jin-Yi Cai and Pinyan Lu

Bounded Queries and the NP Machine Hypothesis
Richard Chang and Suresh Purini

Directed Planar Reachability is in Unambiguous Logspace
Chris Bourke, Raghunath Tewari, and N.V. Vinodchandran

Efficient Arguments without Short PCPs
Yuval Ishai, Eyal Kushilevitz and Rafail Ostrovsky 

Extractors and Condensers from Univariate Polynomials
Venkatesan Guruswami, Christopher Umans, and Salil Vadhan

Halfspace Matrices
Alexander A. Sherstov

Limits on the Hardness of Lattice Problems in l_p Norms
Chris Peikert

Low-Depth Witnesses are Easy to Find
Luis Antunes, Lance Fortnow, Alexandre Pinto and Andre Souto

Lower Bounds for Multi-Player Pointer Jumping
Amit Chakrabarti

Norms, XOR lemmas, and lower bounds for GF(2) polynomials and multiparty protocols
Emanuele Viola and Avi Wigderson

On Approximate Majority and Probabilistic Time
Emanuele Viola

On C-Degrees, H-Degrees and T-Degrees
Wolfgang Merkle and Frank Stephan

On Computation and Communication with Small Bias
Harry Buhrman, Nikolay Vereshchagin, and Ronald de Wolf

On Heuristic Time Hierarchies
Konstantin Pervyshev

On Parameterized Path and Chordless Path Problems
Yijia Chen and Jörg Flum

On derandomizing probabilistic sublinear-time algorithms
Marius Zimand

On the Theory of Matchgate Computations
Jin-Yi Cai and Vinay Choudhary

Parity Problems in Planar Graphs
Mark Braverman, Raghav Kulkarni, and Sambuddha Roy

Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems
Richard Cleve, William Slofstra, Falk Unger, and Sarvagya Upadhyay

Quantum Versus Classical Proofs and Advice
Scott Aaronson and Greg Kuperberg

Quantum t-designs: t-wise independence in the quantum world
Andris Ambainis and Joseph Emerson

S-T Connectivity on Digraphs with Known Stationary Distribution
Kai-Min Chung, Omer Reingold, and Salil Vadhan

Testing Properties of Constraint-Graphs
Shirley Halevy, Oded Lachish, Ilan Newman, and Dekel Tsur

The Communication Complexity of Correlation
Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan

The Complexity of Polynomials and their Coefficient Functions
Guillaume Malod

Time-Space Tradeoffs for Counting NP Solutions Modulo Integers
Ryan Williams

Understanding Parallel Repetition Requires Understanding Foams
Uriel Feige, Guy Kindler, and Ryan O'Donnell