|
Complexity 2007: Conference Schedule |
20.00: Complexity 2007 Welcome Reception
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
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
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
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