25th IEEE Conference on Computational Complexity

June 9 to June 11, 2010
Cambridge, Massachusetts, USA

Local arrangements


Note: Click on a talk title to download the video.


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:00Breakfast 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:30Cocktails and hors d'oeuvres
19:15Keynote speech
20:15Dinner
Thursday, June 10
8:15Breakfast

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