Accepted papers for CCC '05

A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Disjointness by Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson

A Geometric Approach to Information-Theoretic Private Information Retrieval by David Woodruff and Sergey Yekhanin

Average-Case Computations -- Comparing AvgP, HP, and Nearly-P by Arfst Nickelsen and Birgit Schelm

Better Time-Space Lower Bounds for SAT and Related Problems by Ryan Williams

Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy by V. Arvind and Piyush P Kurur and T.C. Vijayaraghavan

Computationally-Private Randomizing Polynomials and Their Applications by Benny Applebaum, Yuval Ishai, Eyal Kushilevitz

Hardness of Max 3SAT with No Mixed Clauses by Venkatesan Guruswami, Subhash Khot

If NP languages are hard on the worst-case then it is easy to find their hard instances by Dan Gutfreund and Ronen Shaltiel and Amnon Ta-Shma

Monotone Circuits for Weighted Threshold Functions by Amos Beimel and Enav Weinreb

More on noncommutative polynomial identity testing by Andrej Bogdanov and Hoeteck Wee

NP with Small Advice by Lance Fortnow and Adam Klivans

New Results on the Complexity of the Middle Bit of Multiplication by Ingo Wegener and Philipp Woelfel

On Constructing Parallel Pseudorandom Generators from One-Way Functions by Emanuele Viola

On the Complexity of Hardness Amplification by Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu

On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas by Richard Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth Vishnoi

On the Hardness of Approximating Multicut and Sparsest-Cut by Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani and D.Sivakumar

On the Ring Isomorphism & Automorphism Problems by Neeraj Kayal, Nitin Saxena

On the Sensitivity of Cyclically-Invariant Boolean Functions by Sourav Chakraborty

On the complexity of succinct zero-sum games by L. Fortnow and R. Impagliazzo and V. Kabanets and C. Umans

On the hardness of distinguishing mixed-state quantum computations by Bill Rosgen and John Watrous

Prior entanglement, message compression and privacy in quantum communication by Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen

Pseudorandom Bits for Constant Depth Circuits with One Arbitrary Symmetric Gate by Emanuele Viola

Pseudorandomness for Approximate Counting and Sampling by Ronen Shaltiel and Chris Umans

Short PCPs verifiiable in polylogarithmic time by Eli Ben-Sasson, Oded Goldriech, Prahladh Harsha, Madhu Sudan and Salil Vadhan

The Complexity of the Inertia and some Closure Properties of GapL by Thanh Minh Hoang and Thomas Thierauf

The quantum adversary method and formula size lower bounds by S. Laplante, T. Lee, and M. Szegedy

Tolerant Versus Intolerant Testing for Boolean Properties by Eldar Fischer and Lance Fortnow

Topology inside NC1 by Eric Allender, Samir Datta, Sambuddha Roy

Toward a Model for Backtracking and Dynamic Programming by M. Alekhnovich, A. Borodin, J. Buresh-Oppenheim, R. Impagliazzo, A. Magen, T. Pitassi

Upper Bounds for Quantum Interactive Proofs with Competing Provers by Gus Gutoski