25th IEEE Conference on Computational Complexity

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

Local arrangements

CCC 2010 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 (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: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 (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