17. CoCo 2002: Montréal, Québec, Canada

Session 1: Joint Session with STOC 2002

• Ran Raz:
  Resolution Lower Bounds for the Weak Pigeonhole Principle. 3
  
• Eli Ben-Sasson:
  Hard Examples for Bounded Depth Frege. 4
  
• Uriel Feige:
  Relations between Average Case Complexity and Approximation Complexity. 5
  
• Jonas Holmerin:
  Vertex Cover on 4-Regular Hyper-graphs Is Hard to Approximate within 2 - \epsilon. 6
  

Session 2: Joint Session with STOC 2002

• Daniele Micciancio:
  Improved Cryptographic Hash Functions with Worst-Case/Average-Case Connection. 9
  
• D. Sivakumar:
  Algorithmic Derandomization via Complexity Theory. 10
  
• Christopher Umans:
  Pseudo-Random Generators for All Hardnesses. 11
  

Session 3: Joint Session with STOC 2002

• Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson:
  Randomness Conductors and Constant-Degree Lossless Expanders. 15
  
• Roy Meshulam, Avi Wigderson:
  Expanders from Symmetric Codes. 16
  
• Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld:
  The Complexity of Approximating the Entropy. 17
  
• Paul Beame, Erik Vee:
  Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems. 18
  
• Ashwin Nayak, Julia Salzman:
  On Communication over an Entanglement-Assisted Quantum Channel. 19
  

Session 4: Joint Session with STOC 2002

• Ryan O'Donnell:
  Hardness Amplification within NP. 23
  
• Ian Agol, Joel Hass, William P. Thurston:
  3-MANIFOLD KNOT GENUS is NP-complete. 24
  
• Subhash Khot:
  On the Power of Unique 2-Prover 1-Round Games. 25
  
• Jeffrey C. Jackson, Adam Klivans, Rocco A. Servedio:
  Learnability beyond AC0. 26
  

Session 5

• Alexander A. Razborov:
  Resolution Lower Bounds for Perfect Matching Principles. 29-38
  
• Stefan S. Dantchev:
  Resolution Width-Size Trade-offs for the Pigeon-Hole Principle. 39-43
  
• Uriel Feige, Daniele Micciancio:
  The Inapproximability of Lattice and Coding Problems with Preprocessing. 44-52
  
• Miklós Ajtai, Ravi Kumar, D. Sivakumar:
  Sampling Short Lattice Vectors and the Closest Lattice Vector Problem. 53-57
  

Invited Address 1

• Lance Fortnow:
  The History of Complexity. 61
  

Session 6

• Frederic Green:
  The Correlation Between Parity and Quadratic Polynomials Mod 3. 65-72
  
• Eldar Fischer, Ilan Newman:
  Functions that have Read-Twice Constant Width Branching Programs are not Necessarily Testable. 73-79
  
• Philipp Woelfel:
  On the Complexity of Integer Multiplication in Branching Programs with Multiple Tests and in Read-Once Branching Programs with Limited Nondeterminism. 80-89
  

Session 7

• Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, D. Sivakumar:
  Information Theory Methods in Communication Complexity. 93-102
  
• Andris Ambainis, Adam Smith, Ke Yang:
  Extracting Quantum Entanglement. 103-112
  
• Markus Bläser:
  Algebras of Minimal Rank over Perfect Fields. 113-122
  

Invited Address 2

• Peter Winkler:
  Rapid Mixing. 125
  

Session 8

• Luca Trevisan, Salil P. Vadhan:
  Pseudorandomness and Average-Case Complexity via Uniform Reductions. 129-138
  
• Manindra Agrawal:
  Pseudo-Random Generators and Structure of Complete Degrees. 139-147
  
• Venkatesan Guruswami, Madhu Sudan:
  Decoding Concatenated Codes using Soft Information. 148-157
  

Survey Talk 1

• John Watrous:
  Arthur and Merlin in a Quantum World. 161
  

Session 9

• Ziv Bar-Yossef, Luca Trevisan, Omer Reingold, Ronen Shaltiel:
  Streaming Computation of Combinatorial Objects. 165-174
  
• Oded Goldreich, Howard J. Karloff, Leonard J. Schulman, Luca Trevisan:
  Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval. 175-183
  
• Amit Deshpande, Rahul Jain, Telikepalli Kavitha, Jaikumar Radhakrishnan, Satyanarayana V. Lokam:
  Better Lower Bounds for Locally Decodable Codes. 184-193
  
• Boaz Barak, Oded Goldreich:
  Universal Arguments and their Applications. 194-203