Accepted papers for CCC '06

A 3-Query Non-Adaptive PCP with Perfect Completeness
Subhash Khot, Rishi Saket

A Generic Time Hierarchy for Semantic Models with One Bit of Advice
Dieter van Melkebeek, Konstantin Pervyshev

A Duality Between Clause Width and Clause Density for SAT
Chris Calabro, Russell Impagliazzo, Ramamohan Paturi

An Isomorphism between Subexponential and Parameterized Complexity Theory
Yijia Chen, Martin Grohe

Circuit lower bounds via Ehrenfeucht-Fraisse games
Michal Koucky, Clemens Lautemann, Sebastian Poloczek, Denis Therien

Constructing Ramsey Graphs from Boolean Function Representations
Parikshit Gopalan

Construction of Low-Degree and Error-Correcting \epsilon-Biased Sets
Amir Shpilka

Derandomization of Probabilistic Auxiliary Pushdown Automata Classes
H. Venkateswaran

Every Linear Threshold Function has a Low-Weight Approximator
Rocco A. Servedio

Exposure-Resilient Extractors
Marius Zimand

C. Behle, K.-J. Lange

Grid Graph Reachability Problems
Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy

Hardness of the Covering Radius Problem on Lattices
Ishay Haviv, Oded Regev

How to get more mileage from randomness extractors
Ronen Shaltiel

Learning Monotone Decision Trees in Polynomial Time
Ryan O'Donnell, Rocco Servedio

Making Hard Problems Harder
Joshua Buresh-Oppenheim, Rahul Santhanam

Minimizing DNF formulas and AC^0_d circuits given a truth table
Eric Allender, Lisa Hellerstein, Paul McCabe, Toni Pitassi, Michael Saks

New lower bounds for Vertex Cover in the Lovasz-Schrijver hierarchy
Iannis Tourlakis

Non-uniform Hardness for NP against Black-Box Samplers
Albert Atserias

On Arthur-Merlin Games and the Possibility of Basing Cryptography on NP-Hardness
Rafael Pass

On Modular Counting with Polynomials
Kristoffer Arnsfelt Hansen

On the Complexity of Numerical Analysis
Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen

Optimal Hardness Results for Maximizing Agreements with Monomials
Vitaly Feldman

Oracles Are Subtle But Not Malicious
Scott Aaronson

Polynomial Identity Testing for Depth 3 Circuits
Neeraj Kayal, Nitin Saxena

QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
Scott Aaronson

Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem
Pranab Sen

Strengths and Weaknesses of Quantum Fingerprinting
Dmitry Gavinsky, Julia Kempe, Ronald de Wolf