List of accepted papers for STOC 2002: Quantum Lower Bound for the Collision Problem Scott Aaronson Approximating The Smallest Grammar: Kolmogorov Complexity in Natural Models Moses Charikar, Eric Lehman, Ding Liu, Manoj Prabhakaran, April Rasala, Amit Sahai and Abhi Shelat Near-Optimal Sparse Fourier Representations via Sampling Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan and Martin J. Strauss Combinatorial Optimization Problems in Self-Assembly Leonard Adleman, Qi Cheng, Ashish Goel, Ming-Deh Huang, David Kempe, Pablo M. de Moisset and Paul W. K. Rothemund The Invasiveness of Off-line Memory Checking Miklos Ajtai Crawling on Web Graphs Colin Cooper and Alan Frieze Optimal Rate-based Scheduling on Multiprocessors Anand Srinivasan and James H. Anderson Space-Efficient Approximate Voronoi Diagrams Sunil Arya, Theocharis Malamatos and David M. Mount Secure Multi-party Quantum Computing Claude Crepeau, Daniel Gottesman and Adam Smith Wait-Free Consensus with Infinite Arrivals James Aspnes, Gauri Shah and Jatin Shah Approximation Algorithms for Minimum-Cost k-Vertex Connected Subgraphs Joseph Cheriyan, Santosh Vempala and Adrian Vetta Expanders from Symmetric Codes Roy Meshulam and Avi Wigderson Girth and Euclidean Distortion Nathan Linial, Avner Magen and Assaf Naor The Complexity of Approximating the Entropy Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar and Ronitt Rubinfeld Strict Polynomial-time in Simulation and Extraction Boaz Barak and Yehuda Lindell Universally Composable Two-party Computation Ran Canetti, Yehuda Lindell, Rafail Ostrovsky and Amit Sahai Remier's Inequality and Tardos' Conjecture Clifford Smyth Selfish Traffic Allocation for Server Farms Artur Czumaj, Piotr Krysta and Berthold Voecking Improved Cryptographic Hash Functions with Worst-case/Average-case Connection Daniele Micciancio On the Complexity of Equilibria Xiaotie Deng, Christos Papadimitriou and Shmuel Safra Tight Security Proofs for the Bounded-Storage Model Stefan Dziembowski and Ueli Maurer Average Case Analysis for Batched Disk Scheduling and Increasing Sequences E.Bachmat New Results on Monotone Dualization and Generating Hypergraph Transversals Thomas Eiter, Georg Gottlob and Kazuhisa Makino Size Space Tradeoffs for Resolution Eli Ben-Sasson Hard Examples for Bounded Depth Frege Eli Ben-Sasson Combinatorial Logarithmic Approximation Algorithm for the Directed Telephone Broadcast Problem Michael Elkin and Guy Kortsarz Time-Space Tradeoffs Multiparty Communication Complexity and Nearest Neighbor Problems Paul Beame and Erik Vee Relations between Average Case Complexity and Approximation Complexity Uriel Feige Clairvoyant Scheduling of Random Walks Peter Gacs Meldable Heaps and Boolean Union-Find Haim Kaplan, Nira Shafrir and Robert E. Tarjan Polynomial-Time Quantum Algorithms for Pell's Equation and the Principal Ideal Problem Sean Hallgren Deterministic Sorting in O(nloglogn) Time and Linear Space Yijie Han 3-manifold knot genus is NP-complete Ian Agol, Joel Hass and William P. Thurston Exact learning of DNF formulas using DNF hypotheses Lisa Hellerstein and Vijay Raghavan The Importance of Being Biased Irit Dinur and Shmuel Safra An Exponential Separation between Regular and General Resolution Michael Alekhnovich, Jan Johannsen, Toniann Pitassi and Alasdair Urquhart Competitive Recommendation Systems Petros Drineas, Iordanis Kerenidis and Prabhakar Raghavan Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2-epsilon Jonas Holmerin Competitive Generalized Auctions Amos Fiat, Andrew V. Goldberg, Jason D. Hartline and Anna R. Karlin Load Balancing in Dynamic Adversarial Systems Elliot Anshelevich, David Kempe and Jon Kleinberg Fitting Algebraic Curves to Noisy Data Sanjeev Arora and Subhash Khot Hardness Results for Approximate Hypergraph Coloring Subhash Khot On the Power of Unique 2-Prover 1-Round Games Subhash Khot Equitable Truth-Revealing Cost Allocations via Primal-Dual-Type Kamal Jain and Vijay Vazirani Cache-Oblivious Priority Queue and Graph Algorithm Applications Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley and J. Ian Munro On Paging with Locality of Reference Susanne Albers, Lene M. Favrholdt and Oliver Giel A New Greedy Approach for Facility Location Problems Kamal Jain, Mohammad Mahdian and Amin Saberi Random Sampling and Approximation of MAX-CSP Problems Noga Alon, W. Fernandez de la Vega, Ravi Kannan and Marek Karpinski A Polynomial Time Algorithm to Approximately Count Contingency Mary Cryan and Martin Dyer Tradeoffs in Probabilistic Packet Marking for IP Traceback Micah Adler Models and Thresholds for Random Constraint Satisfaction Problems Michael Molloy The Glauber Dynamics on the Colourings of a Graph with High Girth and Maximum Degree Michael Molloy Almost All Graphs with Average Degree 4 are 3-Colorable Dimitris Achlioptas and Cristopher Moore Similarity Estimation Techniques from Rounding Algorithms Moses Charikar Recognizing String Graphs in NP Marcus Schaefer, Eric Sedgwick and Daniel Stefankovic Random Sampling in Residual Graphs David R. Karger and Matthew S. Levine On Communication over an Entanglement-Assisted Quantum Channel Ashwin Nayak and Julia Salzman Huffman Coding with Unequal Letter Costs Mordecai J. Golin Claire Kenyon Neal E. Young Concurrent Zero-Knowledge With Timing Revisited Oded Goldreich Hardness Amplification Within NP Ryan O'Donnell Randomness Conductors and Constant-Degree Expansion Beyond the Degree 2 Barrier Michael Capalbo, Omer Reingold, Salil Vadhan and Avi Wigderson Verifying Candidate Matches in Sparse and Wildcard Matching Richard Cole and Ramesh Hariharan Resolution Lower Bounds for the Weak Pigeon Hole Principle Ran Raz On the Complexity of Matrix Product Ran Raz Learnability Beyond AC0 Jeffrey C. Jackson, Adam R. Klivans and Rocco A. Servedio Finding Nearest Neighbors in Growth-restricted Metrics David Karger and Matthias Ruhl On Randomized Online Scheduling Susanne Albers Approximation Schemes for Preemptive Weighted Flow Time Chandra Chekuri and Sanjeev Khanna Approximate Clustering via Core-Sets Mihai Badoiu, Sariel Har-Peled and Piotr Indyk Computing the Betti Numbers of Arrangements Saugata Basu A New average Case Analysis for Completion Time Scheduling Mark Scharbrodt, Thomas Schickinger and Angelika Steger Clifford algebras and Approximating the Permanent Steve Chien, Lars Rasmussen and Alistair Sinclair Approximate Counting of Inversions in a Data Stream Miklos Ajtai, T.S. Jayram, Ravi Kumar and D. Sivakumar Algorithmic derandomization via Complexity Theory D. Sivakumar The Complexity of Choosing an H-Colouring (Nearly) Uniformly at Random Leslie Ann Goldberg, Steven Kelk and Mike Paterson Monotonicity Testing over General Poset Domains Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld and Alex Samorodnitsky Lower Bounds and Competitive Algorithms for On-Line Scheduling of Unit-Size Tasks to Related Machines Spyros Kontogiannis Improved Decremental Algorithms for Transitive Closure and All-pairs Shortest Paths Surender Baswana, Ramesh Hariharan and Sandeep Sen 2-Round Zero Knowledge and Proof Auditors Cynthia Dwork and Larry Stockmeyer Fast Small-space Algorithms for Approximate Histogram Maintenance Anna Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan and Martin J. Strauss Space Lower Bounds for Distance Approximation in the Data Stream Model Michael Saks and Xiaodong Sun On the Composition of Authenticated Byzantine Agreement Ydhuda Lindell, Anna Lysyanskaya and Tal Rabin The Price of Anarchy is Independent of the Network Topology Tim Roughgarden Dynamic Subgraph Connectivity with Geometric Applications Timothy M. Chan Optimal Finger Search Trees in the Pointer Machine Gerth S. Brodal, George Lagogiannis, Christos Makris, Athanasios Tsakalidis and Kostas Tsichlas Pseudo-Random Generators for all Hardnesses Christopher Umans Solving Convex Programs by Random Walks Dimitris Bertsimas and Santosh Vempala Limits to List Decodability of Linear Codes Venkatesan Guruswami Near-optimal Linear-Time Codes for Unique Decoding and New List-Decodable Codes Over Smaller Alphabets Venkatesan Guruswami and Piotr Indyk On the Advantage Over a Random Assignment Johan Hastad and S. Venkatesh A Unified Analysis of Hot Video Schedulers Wun-Tat Chan, Tak-Wah Lam, Hing-Fung Ting and Wai-Ha Wong