Complexity 2007: Conference Schedule

This document was last updated on Friday, June 8th, 2007.

Tuesday, June 12th

20.00: Complexity 2007 Welcome Reception

Wednesday, June 13th

10.30: Welcome

10.40 - 11.15: On derandomizing probabilistic sublinear-time algorithms by Marius Zimand

11.15 - 13.45: Break

13.45 - 14.20: The Communication Complexity of Correlation by Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan

14.20 - 14.55: On Computation and Communication with Small Bias by Harry Buhrman, Nikolay Vereshchagin, and Ronald de Wolf

14.55 - 15.30: Lower Bounds for Multi-Player Pointer Jumping by Amit Chakrabarti

15.30 - 1600: Break

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

16.35 - 17.10: Bounded Queries and the NP Machine Hypothesis by Richard Chang and Suresh Purini

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

18.00 - 19.30 Rump session

Thursday, June 14th

8.50 - 9.25: Time-Space Tradeoffs for Counting NP Solutions Modulo Integers by Ryan Williams

9.25 - 10.00: Halfspace Matrices by Alexander A. Sherstov

10.00 - 10.30: Break

10.30 - 11.25: Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes by Venkatesan Guruswami, Christopher Umans, and Salil Vadhan

11.25 - 13.45: Break

13.45 - 14.20: Perfect Parallel Repetition Theorem for Quantum XOR Proof Systems by Richard Cleve, William Slofstra, Falk Unger, and Sarvagya Upadhyay

14.20 - 14.55: Quantum Versus Classical Proofs and Advice by Scott Aaronson and Greg Kuperberg

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

15.30 - 16.00: Break

16.00 - 16.35: Norms, XOR lemmas, and lower bounds for GF(2) polynomials and multiparty protocols by Emanuele Viola and Avi Wigderson

16.35 - 17.10: On Approximate Majority and Probabilistic Time by Emanuele Viola

17.10 - 17.45: On C-Degrees, H-Degrees and T-Degrees by Wolfgang Merkle and Frank Stephan

21.00: Business meeting

Friday, June 15th

8.50 - 9.25: Understanding Parallel Repetition Requires Understanding Foams by Uriel Feige, Guy Kindler, and Ryan O'Donnell

9.25 - 10.00: The Complexity of Polynomials and their Coefficient Functions by Guillaume Malod

10.00 - 10.30: Break

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

11.05 - 13.45: Break

13.45 - 14.20: Directed Planar Reachability is in Unambiguous Logspace by Chris Bourke, Raghunath Tewari, and N.V. Vinodchandran

14.20 - 14.55: Parity Problems in Planar Graphs by Mark Braverman, Raghav Kulkarni, and Sambuddha Roy

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

15.30 - 16.00: Break

16.00 - 16.35: On Parameterized Path and Chordless Path Problems by Yijia Chen and Jörg Flum

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

17.10 - 17.45 Efficient Arguments without Short PCPs by Yuval Ishai, Eyal Kushilevitz and Rafail Ostrovsky

Saturday, June 16th

8.50 - 9.25: On the Theory of Matchgate Computations by Jin-Yi Cai, Vinay Choudhary and Pinyan Lu

9.25- 10:00: Bases Collapse in Holographic Algorithms by Jin-Yi Cai and Pinyan Lu

10.00 - 10.30: Break

10.30 - 11.05: A New Interactive Hashing Theorem by Iftach Haitner and Omer Reingold

11.05 - 11.40: Limits on the Hardness of Lattice Problems in Lp Norms by Chris Peikert

11.40 - 12.15: On Heuristic Time Hierarchies by Konstantin Pervyshev