| 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 |
| 10:00 | Coffee break
|
10:30
|
No strong parallel repetition with entangled and non-signaling provers
Julia Kempe and Oded Regev |
11:00
|
Derandomized parallel repetition of structured PCPs
Irit Dinur and Or Meir |
11:30
|
Derandomized parallel repetition theorems for free games
Ronen Shaltiel |
| 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 and Akinori Kawachi |
14:30
|
Simple affine extractors using dimension expansion
Matt DeVos and Ariel Gabizon |
15:00
| Derandomizing from random strings
Harry Buhrman, Lance Fortnow ,
Michal Koucky , and Bruno Loff |
| 15:30 | Coffee break
|
16:00
|
On the power of randomized reductions and the checkability of SAT
Mohammad Mahmoody and David Xiao |
16:30
|
A new sampling protocol and applications to basing cryptographic primitives on the hardness of NP
Iftach Haitner ,
Mohammad Mahmoody and David Xiao |
17:00
|
The program-enumeration bottleneck in average-case complexity theory
Luca Trevisan |
| 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 |
| 10:00 | Coffee break
|
10:30
|
Spectral algorithms for unique games
Alexandra Kolla |
11:00
|
A log-space algorithm for reachability in planar acyclic digraphs with few sources
Derrick Stolee,Chris Bourke, and N.V. Vinodchandran |
11:30
|
On the matching problem for special graph classes
Thanh Minh Hoang |
| 12:00 | Lunch break
|
|
Afternoon sessions
chair:
Meena Mahajan |
14:00
|
On the relative strength of pebbling and resolution
Jakob Nordstrom |
14:30
|
Trade-off lower bounds for stack machines
Matei David and Periklis Papakonstantinou |
15:00
|
Symmetry coincides with nondeterminism for time-bounded auxiliary pushdown automata
Eric Allender and Klaus-Joern Lange |
| 15:30 | Coffee break
|
16:00
|
Completely inapproximable monotone and antimonotone parameterized problems
Daniel Marx |
| 16:30 | Rump session
|
| |
Eric Allender
Paul Beame
Kord Eickmeyer
Ranganath Kondapally
Zohar Karnin
Prajakta Nimbhorka
Salil Vadhan
Emanuele Viola
|
| 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 |
| 10:00 | Coffee break
|
10:30
|
The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions
Daniel Kane |
11:00
|
A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions
Ilias Diakonikolas, Rocco Servedio,
Li-Yang Tan, and Andrew Wan |
11:30
|
Fooling functions of halfspaces under product distributions
Parikshit Gopalan,
Ryan O'Donnell, Yi Wu, and David Zuckerman |
| 12:00 | Lunch break
|
|
Afternoon sessions
chair:
Guy Kindler |
14:00
|
Lower bounds for testing function isomorphism
Eric Blais and Ryan O'Donnell |
14:30
|
The partition bound for classical communication complexity and query complexity
Rahul Jainand Hartmut Klauck |
15:00
|
Communication complexity with synchronized clocks
Russell Impagliazzo and
Ryan Williams |
| 15:30 | Coffee break
|
16:00
|
Exact threshold circuits
Kristoffer Arnsfelt Hansen and Vladimir Podolskii |
16:30
|
Relationless completeness and separations
Pavel Hrubes, Avi Wigderson, and Amir Yehudayoff |
17:00
|
On matrix rigidity and locally self-correctable codes
Zeev Dvir |
| 17:30 | End of the conference
|