21. CCC 2006: Prague, Czech Republic

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 AC⁰_d 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