CCC 2010: Accepted papers
and invited speakers

Invited speakers

25th anniversary banquet speaker: Juris Hartmanis

Invited technical speakers: Subhash Khot, Ran Raz, Oded Regev

Accepted papers (in order of submission)

On the relative strength of pebbling and resolution
Jakob Nordstrom

Simple affine extractors using dimension expansion
Matt DeVos and Ariel Gabizon

No strong parallel repetition with entangled and non-signaling provers
Julia Kempe and Oded Regev

Symmetry coincides with nondeterminism for time-bounded auxiliary pushdown automata
Eric Allender and Klaus-Joern Lange

On the matching problem for special graph classes
Thanh Minh Hoang

On matrix rigidity and locally self-correctable codes
Zeev Dvir

Relationless completeness and separations
Pavel Hrubes, Avi Wigderson, and Amir Yehudayoff

The partition bound for classical communication complexity and query complexity
Rahul Jain and Hartmut Klauck

The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions
Daniel Kane

Completely inapproximable monotone and antimonotone parameterized
Daniel Marx

A log-space algorithm for reachability in planar acyclic digraphs with few sources
Derrick Stolee, Chris Bourke, and N.V. Vinodchandran

Spectral algorithms for unique games
Alexandra Kolla

Derandomizing Arthur-Merlin games and approximate counting implies exponential-size lower bounds
Dan Gutfreund and Akinori Kawachi

Exact threshold circuits
Kristoffer Arnsfelt Hansen and Vladimir Podolskii

The program-enumeration bottleneck in average-case complexity theory
Luca Trevisan

Derandomized parallel repetition theorems for free games
Ronen Shaltiel

A new sampling protocol and applications to basing cryptographic primitives on the hardness of NP
Iftach Haitner, Mohammad Mahmoody, and David Xiao

Derandomized parallel repetition of structured PCPs
Irit Dinur and Or Meir

A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions
Ilias Diakonikolas, Rocco Servedio, Li-Yang Tan, and Andrew Wan

Communication complexity with synchronized clocks
Russell Impagliazzo and Ryan Williams

Lower bounds for testing function isomorphism
Eric Blais and Ryan O'Donnell

Derandomizing from random strings
Harry Buhrman, Lance Fortnow, Michal Koucky, and Bruno Loff

On the power of randomized reductions and the checkability of SAT
Mohammad Mahmoody and David Xiao

Trade-off lower bounds for stack machines
Matei David and Periklis Papakonstantinou

Fooling functions of halfspaces under product distributions
Parikshit Gopalan, Ryan O'Donnell, Yi Wu, and David Zuckerman