default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID21st CCC 2006: Prague, Czech Republic
- 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic. IEEE Computer Society 2006, ISBN 0-7695-2596-2
Introduction
- Preface.
- Committees.
- Reviewers.
- Awards.
Session 1
- Pavel Pudlák:
Godel and Computations (Abstract). 3-5
Session 2
- Neeraj Kayal, Nitin Saxena
:
Polynomial Identity Testing for Depth 3 Circuits. 9-17 - Rocco A. Servedio:
Every Linear Threshold Function has a Low-Weight Approximator. 18-32
Session 3
- Amir Shpilka:
Constructions of Low-Degree and Error-Correcting in-Biased Generators. 33-45 - Ronen Shaltiel:
How to Get More Mileage from Randomness Extractors. 46-60 - Marius Zimand:
Exposure-Resilient Extractors. 61-72
Session 4
- Joshua Buresh-Oppenheim, Rahul Santhanam:
Making Hard Problems Harder. 73-87 - Albert Atserias:
Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries. 88-95 - Rafael Pass:
Parallel Repetition of Zero-Knowledge Proofs and the Possibility of Basing Cryptography on NP-Hardness. 96-110
Session 5
- Avi Wigderson:
Applications of the Sum-Product Theorem in Finite Fields. 111
Session 6
- Parikshit Gopalan:
Constructing Ramsey Graphs from Boolean Function Representations. 115-128 - Dieter van Melkebeek, Konstantin Pervyshev:
A Generic Time Hierarchy for Semantic Models with One Bit of Advice. 129-144
Session 7
- Ishay Haviv, Oded Regev:
Hardness of the Covering Radius Problem on Lattices. 145-158 - Subhash Khot, Rishi Saket:
A 3-Query Non-Adaptive PCP with Perfect Completeness. 159-169 - Iannis Tourlakis:
New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy. 170-182
Session 8
- Christoph Behle, Klaus-Jörn Lange:
FO[<]-Uniformity. 183-189 - Michal Koucký, Clemens Lautemann, Sebastian Poloczek, Denis Thérien:
Circuit Lower Bounds via Ehrenfeucht-Fraisse Games. 190-201 - Kristoffer Arnsfelt Hansen:
On Modular Counting with Polynomials. 202-212
Session 9
- Ryan O'Donnell, Rocco A. Servedio:
Learning Monotone Decision Trees in Polynomial Time. 213-225 - Vitaly Feldman:
Optimal Hardness Results for Maximizing Agreements with Monomials. 226-236
Session 10
- Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing DNF Formulas and AC0d Circuits Given a Truth Table. 237-251 - Chris Calabro, Russell Impagliazzo, Ramamohan Paturi:
A Duality between Clause Width and Clause Density for SAT. 252-260
Session 11
- Scott Aaronson:
QMA/qpoly \subseteq PSPACE/poly: De-Merlinizing Quantum Protocols. 261-273 - Pranab Sen:
Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem. 274-287 - Dmitry Gavinsky, Julia Kempe, Ronald de Wolf:
Strengths and Weaknesses of Quantum Fingerprinting. 288-298
Session 12
- Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy:
Grid Graph Reachability Problems. 299-313 - Yijia Chen, Martin Grohe:
An Isomorphism between Subexponential and Parameterized Complexity Theory. 314-330
Session 13
- Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen:
On the Complexity of Numerical Analysis. 331-339 - Scott Aaronson:
Oracles Are Subtle But Not Malicious. 340-354 - H. Venkateswaran:
Derandomization of Probabilistic Auxiliary Pushdown Automata Classes. 355-370
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.
last updated on 2025-07-08 20:53 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
