Accepted papers for CCC '03

Title: Quantum Certificate Complexity
Author(s): Scott Aaronson

Title: Derandomization and Distinguishing Complexity.
Author(s): Eric Allender, Michal Koucky, Detlef Ronneburger, Sambuddha Roy.

Title: Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness
Author(s): Amit Chakrabarti and Subhash Khot and Xiaodong Sun

Title: Uniform Hardness vs. Randomness Tradeoffs for Arthur-Merlin Games
Author(s): Dan Gutreund and Ronen Shaltiel and Amnon Ta-Shma

Title: Universal Languages and the Power of Diagonalization
Author(s): Alan Nash and Russell Impagliazzo and Jeff Remmel

Title: Extracting the Mutual Information for a Triple of Binary Strings
Author(s): Andrei E. Romashchenko

Title: A Combinatorial Characterization of Resolution Width
Author(s): Albert Atserias and Victor Dalmau

Title: Quantum decision trees and semidefinite programming
Author(s): Howard Barnum and Michael Saks and Mario Szegedy

Title: Memoization and DPLL: Formula Caching Proof Systems
Author(s): Paul Beame and Russell Impagliazzo and Toniann Pitassi and Nathan Segerlind

Title: Three-Query PCPs with Perfect Completeness over non-Boolean Domains
Author(s): Lars Engebretsen and Jonas Holmerin

Title: Are Cook and Karp Ever the Same?
Author(s): Richard Beigel and Lance Fortnow

Title: Disjoint NP-Pairs
Author(s): Christian Glaßer and Alan L. Selman and Samik Sengupta and Liyu Zhang

Title: Bounded Nondeterminism and Alternation in Parameterized Complexity Theory
Author(s): Yijia Chen and Joerg Flum and Martin Grohe

Title: A Strong Inapproximability Result for a Generalization of Minimum Bisection.
Author(s): Jonas Holmerin and Subhash Khot

Title: The complexity of Unique k-SAT: An isolation lemma for k-CNFs
Author(s): Chris Calabro and Russell Impagliazzo and Valentine Kabanets and Ramamohan Paturi

Title: Rectangle Size Bounds and Threshold Covers in Communication Complexity
Author(s): Hartmut Klauck

Title: The complexity of stochastic sequences
Author(s): Wolfgang Merkle

Title: A zero-one law for RP
Author(s): Russell Impagliazzo and Philippe Moser

Title: Improved Inapproximability of Lattice and Coding Problems with Preprocessing
Author(s): Oded Regev

Title: Vertex Cover Might be Hard to Approximate to within 2-e
Author(s): Subhash Khot and Oded Regev

Title: Extremal properties of polynomial threshold functions
Author(s): Ryan O'Donnell and Rocco Servedio

Title: Proving SAT does not have Small Circuits with an Application to the Two Queries Problem
Author(s): Lance Fortnow and A. Pavan and Samik Sengupta

Title: Lower bounds for predecessor searching in the cell probe model
Author(s): Pranab Sen

Title: Holographic Proofs and Derandomization
Author(s): Rahul Santhanam and Dieter van Melkebeek

Title: Minimization of Decision Trees is Hard to Approximate
Author(s): Detlef Sieling

Title: Optimal Separation of EROW and CROW PRAMs
Author(s): Navin Goyal and Michael Saks and S. Venkatesh

Title: List decoding with side information
Author(s): Venkatesan Guruswami

Title: Hardness vs. Randomness within Uniform AC0
Author(s): Emanuele Viola

Title: On Statistical Query Sampling and NMR Quantum Computing
Author(s): Avrim Blum and Ke Yang