Papers Accepted to CCC 2007 --------------------------- 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