Complexity 2008: Conference Schedule

Sunday, June 22nd

6:00-9:00 PM Complexity 2008 Welcome Reception

Monday, June 23rd

9:00- 9:30 NP-hard sets are exponentially dense unless coNP is contained in NP/poly
Harry Buhrman and John M. Hitchcock
9:30-10:00 Approximisation of natural W[P]-complete minimisation problems is hard
Kord Eickmeyer, Martin Grohe, and Magdalena Grüber
10:30-11:00 Hardness amplification within NP against deterministic algorithms
Parikshit Gopalan and Venkatesan Guruswami
11:00-11:30 Amplifying Lower Bounds by Means of Self-Reducibility
Eric Allender and Michal Koucký
11:30-12:00 Amplifying ZPPSAT[1] and the Two Queries Problem
Richard Chang and Suresh Purini
2:00-2:30 Learning complexity vs. communication complexity
Nathan Linial and Adi Shraibman
2:30-3:00 Communication Complexity under Product and Nonproduct Distributions
Alexander A. Sherstov
3:30-4:00 A direct product theorem for discrepancy
Troy Lee, Adi Shraibman, and Robert Špalek
4:00-4:30 Disjointness is hard in the multi-party number-on-the-forehead model
Troy Lee and Adi Shraibman
4:45-6:00 Rump Session

Tuesday, June 24th

9:00-9:30 Constant Width Planar Branching Programs Characterize ACC0 in Quasipolynomial Size
Kristoffer Arnsfelt Hansen
9:30-10:00 On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs
Nathan Segerlind
10:30-11:00 Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions
Alexander A. Sherstov
11:00-11:30 The sum of d small-bias generators fools polynomials of degree d
Emanuele Viola
11:30-12:00 Lower Bounds and Separations for Constant Depth Multilinear Circuits
Ran Raz and Amir Yehudayoff
2:00-2:30 Noisy Interpolating Sets for Low Degree Polynomials
Zeev Dvir and Amir Shpilka
2:30-3:00 Constraint Logic: A Uniform Framework for Modeling Computation as Games
Erik D. Demaine and Robert A. Hearn
3:30-4:00 Soft decoding, dual BCH codes, and better epsilon-biased list-decodable codes
Venkatesan Guruswami and Atri Rudra
4:00-4:30 Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers
Kiran S. Kedlaya and Sergey Yekhanin
4:45-7:00 Business Meeting

Wednesday, June 25th

9:00-9:30 Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi- Prover Interactive Proof Systems
Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun, and Andrew C.-C. Yao
9:30-10:00 The quantum moment problem and bounds on entangled multiprover games
Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner, and Stephanie Wehner
10:30-11:00 Using Entanglement in Quantum Multi-Prover Interactive Proofs
Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, and Thomas Vidick
11:00-11:30 The Power of Unentanglement
Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor
11:30-12:00 The Multiplicative Quantum Adversary
Robert Špalek
2:00-2:30 Approximation Resistant Predicates From Pairwise Independence
Per Austrin and Elchanan Mossel
2:30-3:00 2-Transitivity is Insufficient for Local Testability
Elena Grigorescu, Tali Kaufman, and Madhu Sudan
3:30-4:00 New results on Noncommutative and Commutative Polynomial Identity Testing
V. Arvind, Partha Mukhopadhyay, and Srikanth Srinivasan
4:00-4:30 Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in
Zohar S. Karnin and Amir Shpilka

Thursday, June 26th

9:00-9:30 Quantum Expanders: Motivation and Constructions
Avraham Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma
9:30-10:00 Towards Dimension Expanders Over Finite Fields
Zeev Dvir and Amir Shpilka
10:30-11:00 Detecting Rational Points on Hypersurfaces over Finite Fields
Swastik Kopparty and Sergey Yekhanin
11:00-11:30 Randomized Individual Communication Complexity
Harry Buhrman, Michal Koucký, and Nikolai Vereshchagin
11:30-12:00 Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity
Dmitry Gavinsky and Pavel Pudlák