![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
25th CCC 2010: Cambridge, Massachusetts, USA
- Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, 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
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.