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 resolutionJakob 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
problems
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