## Complexity 2008: Conference Schedule |

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^{0} 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 |