Complexity 2008: Conference Schedule

Sunday, June 22nd

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

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

Break

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 ZPP^SAT[1] and the Two Queries Problem
	Richard Chang and Suresh Purini

Lunch

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

Break

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

9:00-9:30	Constant Width Planar Branching Programs Characterize ACC⁰ 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

Break

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

Lunch

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

Break

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

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

Break

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

Lunch

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
Break


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

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

Break

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