Program
All events will be held in Maxwell Dworkin except the Happy Hour and the Banquet.| Tuesday, June 8 | |
| 15:00-19:00 | Registration |
| 17:30-19:30 | Happy Hour at John Harvard's Brew House |
| Wednesday, June 9 | |
| 8:00 | Breakfast and registration |
Morning sessions chair: Sanjeev Arora | |
| 09:00 |
Parallel repetition of two-prover games (survey talk)
Ran Raz (Weizmann I.) |
| 10:00 | Coffee break |
| 10:30 | No strong parallel
repetition with entangled and non-signaling
provers Julia Kempe (Tel Aviv U.) and Oded Regev (Tel Aviv U.) |
| 11:00 |
Derandomized parallel repetition of structured PCPs Irit Dinur (Weizmann I.) and Or Meir (Weizmann I.) |
| 11:30 |
Derandomized parallel repetition theorems for free games Ronen Shaltiel (U. Haifa) |
| 12:00 | Lunch break |
Afternoon sessions chair: Emanuele Viola | |
| 14:00 |
Derandomizing Arthur-Merlin games and approximate counting implies
exponential-size lower bounds Dan Gutfreund (IBM Research - Haifa) and Akinori Kawachi (Tokyo Institute of Technology) |
| 14:30 |
Simple affine extractors using dimension expansion Matt DeVos (Simon Fraser U.) and Ariel Gabizon (Columbia U. & U. Texas - Austin) |
| 15:00 |
Derandomizing from random strings Harry Buhrman (CWI & U. Amsterdam), Lance Fortnow (Northwestern U.), Michal Koucky (Czech Academy of Sciences), and Bruno Loff (CWI) |
| 15:30 | Coffee break |
| 16:00 |
On the power of randomized reductions and the checkability of SAT Mohammad Mahmoody (Princeton U.) and David Xiao (U. Paris-Sud) |
| 16:30 |
A new sampling protocol and applications to basing cryptographic
primitives on the hardness of NP Iftach Haitner (Microsoft Research - New England), Mohammad Mahmoody (Princeton U.), and David Xiao (U. Paris-Sud) |
| 17:00 |
The program-enumeration bottleneck in average-case complexity theory Luca Trevisan (U. California - Berkeley & Stanford U.) |
| 17:30 | Break |
| 25th anniversary
banquet at Harvard
Faculty Club. Keynote speaker: Juris Hartmanis | |
| 18:30 | Cocktails and hors
d'oeuvres |
| 19:15 | Keynote speech |
| 20:15 | Dinner |
| Thursday, June 10 | |
| 8:15 | Breakfast |
Morning sessions chair: Venkatesan Guruswami | |
| 09:00 |
On the unique games conjecture (survey talk) Subhash Khot (NYU) |
| 10:00 | Coffee break |
| 10:30 |
Spectral algorithms for unique games Alexandra Kolla (IAS) |
| 11:00 |
A log-space algorithm for reachability in planar acyclic digraphs
with few sources Derrick Stolee (U. Nebraska - Lincoln), Chris Bourke (U. Nebraska - Lincoln), and N.V. Vinodchandran (U. Nebraska - Lincoln) |
| 11:30 |
On the matching problem for special graph classes Thanh Minh Hoang (U. Ulm) |
| 12:00 | Lunch break |
Afternoon sessions chair: Meena Mahajan | |
| 14:00 |
On the relative strength of pebbling and resolution Jakob Nordstrom (MIT) |
| 14:30 |
Trade-off lower bounds for stack machines Matei David (U. Toronto) and Periklis Papakonstantinou (U. Toronto) |
| 15:00 |
Symmetry coincides with nondeterminism for time-bounded auxiliary
pushdown automata Eric Allender (Rutgers U.) and Klaus-Joern Lange (U. Tuebingen) |
| 15:30 | Coffee break |
| 16:00 |
Completely inapproximable monotone and antimonotone parameterized
problems Daniel Marx (Tel Aviv U.) |
| 16:30 | Rump session |
| 17:30 | Break |
| 20:30 | Business meeting |
| Friday, June 11 | |
| 8:15 | Breakfast |
Morning sessions chair: Amir Shpilka | |
| 09:00 |
The learning with errors problem (survey talk) Oded Regev (Tel Aviv U.) |
| 10:00 | Coffee break |
| 10:30 |
The Gaussian surface area and noise sensitivity of degree-d polynomial
threshold functions Daniel Kane (Harvard U.) |
| 11:00 |
A regularity lemma, and low-weight approximators, for low-degree
polynomial threshold functions Ilias Diakonikolas (Columbia U.), Rocco Servedio (Columbia U.), Li-Yang Tan (Columbia U.), and Andrew Wan (Columbia U.) |
| 11:30 |
Fooling functions of halfspaces under product distributions Parikshit Gopalan (Microsoft Research - Silicon Valley), Ryan O'Donnell (CMU), Yi Wu (CMU), and David Zuckerman (U. Texas - Austin) |
| 12:00 | Lunch break |
Afternoon sessions chair: Guy Kindler | |
| 14:00 |
Lower bounds for testing function isomorphism Eric Blais (CMU) and Ryan O'Donnell (CMU) |
| 14:30 |
The partition bound for classical communication complexity and
query complexity Rahul Jain (National U. Singapore) and Hartmut Klauck (National U. Singapore) |
| 15:00 |
Communication complexity with synchronized clocks Russell Impagliazzo (IAS & U. California - San Diego) and Ryan Williams (IBM Research - Almaden) |
| 15:30 | Coffee break |
| 16:00 |
Exact threshold circuits Kristoffer Arnsfelt Hansen (Aarhus U.) and Vladimir Podolskii (Steklov Mathematical I.) |
| 16:30 |
Relationless completeness and separations Pavel Hrubes (Princeton U.), Avi Wigderson (IAS), and Amir Yehudayoff (IAS) |
| 17:00 |
On matrix rigidity and locally self-correctable codes Zeev Dvir (IAS) |
| 17:30 | End of the conference
|