20. CCC 2005: San Jose, CA, USA

20th Annual IEEE Conference on Computational Complexity (CCC 2005), 11-15 June 2005, San Jose, CA, USA. IEEE Computer Society 2005, ISBN 0-7695-2364-1 BibTeX

Introduction

Preface.
Electronic Edition (link) BibTeX
Committees.
Electronic Edition (link) BibTeX
Awards.
Electronic Edition (link) BibTeX

Session 1

Neeraj Kayal, Nitin Saxena:
On the Ring Isomorphism and Automorphism Problems. 2-12
Electronic Edition (link) BibTeX
Vikraman Arvind, Piyush P. Kurur, T. C. Vijayaraghavan:
Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy. 13-27
Electronic Edition (link) BibTeX
Thanh Minh Hoang, Thomas Thierauf:
The Complexity of the Inertia and Some Closure Properties of GapL. 28-37
Electronic Edition (link) BibTeX

Session 2 (Best Student Paper Award)

Ryan Williams:
Better Time-Space Lower Bounds for SAT and Related Problems. 40-49
Electronic Edition (link) BibTeX

Session 3

Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson:
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. 52-66
Electronic Edition (link) BibTeX
Amos Beimel, Enav Weinreb:
Monotone Circuits for Weighted Threshold Functions. 67-75
Electronic Edition (link) BibTeX
Sophie Laplante, Troy Lee, Mario Szegedy:
The Quantum Adversary Method and Classical Formula Size Lower Bounds. 76-90
Electronic Edition (link) BibTeX

Session 4

Andrej Bogdanov, Hoeteck Wee:
More on Noncommutative Polynomial Identity Testing. 92-99
Electronic Edition (link) BibTeX
Ingo Wegener, Philipp Woelfel:
New Results on the Complexity of the Middle Bit of Multiplication. 100-110
Electronic Edition (link) BibTeX

Session 5

Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi:
On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas. 112-119
Electronic Edition (link) BibTeX
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
Short PCPs Verifiable in Polylogarithmic Time. 120-134
Electronic Edition (link) BibTeX
Eldar Fischer, Lance Fortnow:
Tolerant Versus Intolerant Testing for Boolean Properties. 135-140
Electronic Edition (link) BibTeX

Session 6 (Invited Lecture)

Understanding "Understanding": Steps toward a Mathematical Scientific Theory of Consciousness

Session 7

Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar:
On the Hardness of Approximating Multicut and Sparsest-Cut. 144-153
Electronic Edition (link) BibTeX
Venkatesan Guruswami, Subhash Khot:
Hardness of Max 3SAT with No Mixed Clauses. 154-162
Electronic Edition (link) BibTeX
Sourav Chakraborty:
On the Sensitivity of Cyclically-Invariant Boolean Functions. 163-167
Electronic Edition (link) BibTeX

Session 8

Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu:
On the Complexity of Hardness Amplification. 170-182
Electronic Edition (link) BibTeX
Emanuele Viola:
On Constructing Parallel Pseudorandom Generators from One-Way Functions. 183-197
Electronic Edition (link) BibTeX
Emanuele Viola:
Pseudorandom Bits for Constant Depth Circuits with Few Arbitrary Symmetric Gates. 198-209
Electronic Edition (link) BibTeX

Session 9 (Best Paper Award)

Ronen Shaltiel, Christopher Umans:
Pseudorandomness for Approximate Counting and Sampling. 212-226
Electronic Edition (link) BibTeX

Session 10

Lance Fortnow, Adam R. Klivans:
NP with Small Advice. 228-234
Electronic Edition (link) BibTeX
Arfst Nickelsen, Birgit Schelm:
Average-Case Computations - Comparing AvgP, HP, and Nearly-P. 235-242
Electronic Edition (link) BibTeX
Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma:
If NP Languages are Hard on the Worst-Case Then It is Easy to Find Their Hard Instances. 243-257
Electronic Edition (link) BibTeX

Session 11

Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
Computationally Private Randomizing Polynomials and Their Applications. 260-274
Electronic Edition (link) BibTeX
David P. Woodruff, Sergey Yekhanin:
A Geometric Approach to Information-Theoretic Private Information Retrieval. 275-284
Electronic Edition (link) BibTeX
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen:
Prior Entanglement, Message Compression and Privacy in Quantum Communication. 285-296
Electronic Edition (link) BibTeX

Session 12

Eric Allender, Samir Datta, Sambuddha Roy:
Topology Inside NC¹. 298-307
Electronic Edition (link) BibTeX
Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi:
Toward a Model for Backtracking and Dynamic Programming. 308-322
Electronic Edition (link) BibTeX
Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans:
On the Complexity of Succinct Zero-Sum Games. 323-332
Electronic Edition (link) BibTeX

Session 13

Gus Gutoski:
Upper Bounds for Quantum Interactive Proofs with Competing Provers. 334-343
Electronic Edition (link) BibTeX
Bill Rosgen:
On the Hardness of Distinguishing Mixed-State Quantum Computations. 344-354
Electronic Edition (link) BibTeX