The following papers have been accepted to the Conference on Computational Complexity 2002. ----------------------------------------------- Algebras of minimal rank over perfect fields Markus Blaeser Pseudo-random Generators and Structure of Complete Degrees Manindra Agrawal Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate within 2-\epsilon Jonas Holmerin Universal Arguments and their Applications Boaz Barak and Oded Goldreich Learnability Beyond AC0 Jeffrey C. Jackson, Adam R. Klivans and Rocco A. Servedio Hardness Amplification Within NP Ryan O'Donnell The Correlation Between Parity and Quadratic Polynomials Mod 3 Frederic Green Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest Neighbor Problems Paul Beame and Erik Vee Functions that have read-twice, constant width, branching programs are not necessarily testable Eldar Fischer and Ilan Newman On communication over an entanglement-assisted quantum channel Ashwin Nayak and Julia Salzman Decoding Concatenated Codes using Soft Information Venkatesan Guruswami and Madhu Sudan On the Power of Unique 2-Prover 1-Round Games Subhash Khot Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval Oded Goldreich and Howard Karloff and Leonard Schulman and Luca Trevisan Resolution lower bounds for the weak pigeon hole principle Ran Raz Streaming Computation of Combinatorial Objects Ziv Bar-Yossef and Omer Reingold and Ronen Shaltiel and Luca Expanders from Symmetric Codes Roy Meshulam and Avi Wigderson The inapproximability of lattice and coding problems with preprocessing Uriel Feige, Daniele Micciancio Resolution Lower Bounds for Perfect Matching Principles Alexander A. Razborov Relations between average case complexity and approximation complexity Uriel Feige Algorithmic derandomization via Complexity Theory D. Sivakumar Hard Examples for Bounded Depth Frege Eli Ben-Sasson Sampling short lattice vectors and the closest lattice vector problem Miklos Ajtai and Ravi Kumar and D. Sivakumar Resolution width-size trade-offs for the Pigeon-Hole Principle Stefan Dantchev On the Complexity of Integer Multiplication in Branching Programs with Multiple Tests and in Read-Once Branching Programs with Limited Nondeterminism Philipp Woelfel 3-MANIFOLD KNOT GENUS is NP-complete Ian Agol, Joel Hass and William P. Thurston Randomness Conductors and Constant-Degree Expansion Beyond the... Michael Capalbo and Omer Reingold and Salil Vadhan and Avi Pseudo-Random Generators for all Hardnesses Christopher Umans Information Theory Methods in Communication Complexity Ziv Bar-Yossef and T.S. Jayram and Ravi Kumar and D. Sivakumar The complexity of approximating the entropy Tugkan Batu and Sanjoy Dasgupta and Ravi Kumar and Ronitt Better Lower Bounds for Locally Decodable Codes Amit Deshpande and Rahul Jain and T Kavita and Satyanarayana V. Pseudorandomness and Average-Case Complexity with Uniform Reductions Luca Trevisan and Salil Vadhan Improved cryptographic hash functions with worst-case/average-case connection Daniele Micciancio Extracting Quantum Entanglement (General Entanglement Purification Protocols) Andris Ambainis and Ke Yang