25. CCC 2010:
Cambridge, Massachusetts, USA
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, June 9-12, 2010.
IEEE Computer Society 2010, ISBN 978-0-7695-4060-3 
- Ran Raz:
Parallel Repetition of Two Prover Games (Invited Survey).
3-6
- Julia Kempe, Oded Regev:
No Strong Parallel Repetition with Entangled and Non-signaling Provers.
7-15
- Irit Dinur, Or Meir:
Derandomized Parallel Repetition of Structured PCPs.
16-27
- Ronen Shaltiel:
Derandomized Parallel Repetition Theorems for Free Games.
28-37
- Dan Gutfreund, Akinori Kawachi:
Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds.
38-49
- Matt DeVos, Ariel Gabizon:
Simple Affine Extractors Using Dimension Expansion.
50-57
- Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff:
Derandomizing from Random Strings.
58-63
- Mohammad Mahmoody, David Xiao:
On the Power of Randomized Reductions and the Checkability of SAT.
64-75
- Iftach Haitner, Mohammad Mahmoody, David Xiao:
A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP.
76-87
- Luca Trevisan:
The Program-Enumeration Bottleneck in Average-Case Complexity Theory.
88-95
- Subhash Khot:
On the Unique Games Conjecture (Invited Survey).
99-121
- Alexandra Kolla:
Spectral Algorithms for Unique Games.
122-130
- Derrick Stolee, Chris Bourke, N. V. Vinodchandran:
A Log-Space Algorithm for Reachability in Planar Acyclic Digraphs with Few Sources.
131-138
- Thanh Minh Hoang:
On the Matching Problem for Special Graph Classes.
139-150
- Jakob Nordström:
On the Relative Strength of Pebbling and Resolution.
151-162
- Matei David, Periklis A. Papakonstantinou:
Trade-Off Lower Bounds for Stack Machines.
163-171
- Eric Allender, Klaus-Jörn Lange:
Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata.
172-180
- Dániel Marx:
Completely Inapproximable Monotone and Antimonotone Parameterized Problems.
181-187
- Oded Regev:
The Learning with Errors Problem (Invited Survey).
191-204
- Daniel M. Kane:
The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions.
205-210
- Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan:
A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions.
211-222
- Parikshit Gopalan, Ryan O'Donnell, Yi Wu, David Zuckerman:
Fooling Functions of Halfspaces under Product Distributions.
223-234
- Eric Blais, Ryan O'Donnell:
Lower Bounds for Testing Function Isomorphism.
235-246
- Rahul Jain, Hartmut Klauck:
The Partition Bound for Classical Communication Complexity and Query Complexity.
247-258
- Russell Impagliazzo, Ryan Williams:
Communication Complexity with Synchronized Clocks.
259-269
- Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii:
Exact Threshold Circuits.
270-279
- Pavel Hrubes, Avi Wigderson, Amir Yehudayoff:
Relationless Completeness and Separations.
280-290
- Zeev Dvir:
On Matrix Rigidity and Locally Self-Correctable Codes.
291-298
Last update Sat May 18 02:20:08 2013
CET by the DBLP Team — 
Data released under the ODC-BY 1.0 license — See also our legal information page
