20. CCC 2005: San Jose, CA, USA

Introduction

• Preface.
  
• Committees.
  
• Awards.
  

Session 1

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

Session 2 (Best Student Paper Award)

• Ryan Williams:
  Better Time-Space Lower Bounds for SAT and Related Problems. 40-49
  

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
  
• Amos Beimel, Enav Weinreb:
  Monotone Circuits for Weighted Threshold Functions. 67-75
  
• Sophie Laplante, Troy Lee, Mario Szegedy:
  The Quantum Adversary Method and Classical Formula Size Lower Bounds. 76-90
  

Session 4

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

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
  
• Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan:
  Short PCPs Verifiable in Polylogarithmic Time. 120-134
  
• Eldar Fischer, Lance Fortnow:
  Tolerant Versus Intolerant Testing for Boolean Properties. 135-140
  

Session 6 (Invited Lecture)

Session 7

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

Session 8

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

Session 9 (Best Paper Award)

• Ronen Shaltiel, Christopher Umans:
  Pseudorandomness for Approximate Counting and Sampling. 212-226
  

Session 10

• Lance Fortnow, Adam R. Klivans:
  NP with Small Advice. 228-234
  
• Arfst Nickelsen, Birgit Schelm:
  Average-Case Computations - Comparing AvgP, HP, and Nearly-P. 235-242
  
• 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
  

Session 11

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

Session 12

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

Session 13

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