| 2002 | Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States. | Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen |
| 2002 | Erratum to "Vickrey Pricing and Shortest Paths: What is an Edge Worth?". | John Hershberger, Subhash Suri |
| 2002 | Integer Sorting in 0(n sqrt (log log n)) Expected Time and Linear Space. | Yijie Han, Mikkel Thorup |
| 2002 | Locally Testable Codes and PCPs of Almost-Linear Length. | Oded Goldreich, Madhu Sudan |
| 2002 | Zero-Knowledge. | Oded Goldreich |
| 2002 | On-Line End-to-End Congestion Control. | Naveen Garg, Neal E. Young |
| 2002 | Fast Approximation Algorithms for Fractional Steiner Forest and Related Problems. | Naveen Garg, Rohit Khandekar |
| 2002 | Dependent Rounding in Bipartite Graphs. | Rajiv Gandhi, Samir Khuller, Srinivasan Parthasarathy, Aravind Srinivasan |
| 2002 | A Simple Algorithmic Characterization of Uniform Solvability. | Eli Gafni |
| 2002 | On Random Symmetric Travelling Salesman Problems. | Alan M. Frieze |
| 2002 | Implicit B-Trees: New Results for the Dictionary Problem. | Gianni Franceschini, Roberto Grossi, J. Ian Munro, Linda Pagli |
| 2002 | The Parameterized Complexity of Counting Problems. | Jrg Flum, Martin Grohe |
| 2002 | Testing Juntas. | Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky |
| 2002 | Decoding Turbo-Like Codes via Linear Programming. | Jon Feldman, David R. Karger |
| 2002 | Graphs with Tiny Vector Chromatic Numbers and Huge Chromatic Numbers. | Uriel Feige, Michael Langberg, Gideon Schechtman |
| 2002 | Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks. | Guy Even, Zvi Lotker, Dana Ron, Shakhar Smorodinsky |
| 2002 | The 3-XORSAT Threshold. | Olivier Dubois, Jacques Mandler |
| 2002 | On the (non)Universality of the One-Time Pad. | Yevgeniy Dodis, Joel Spencer |
| 2002 | The Hardness of 3 - Uniform Hypergraph Coloring. | Irit Dinur, Oded Regev, Clifford D. Smyth |
| 2002 | Market Equilibrium via a Primal-Dual-Type Algorithm. | Nikhil R. Devanur, Christos H. Papadimitriou, Amin Saberi, Vijay V. Vazirani |
| 2002 | Abstract Combinatorial Programs and Efficient Property Testers. | Artur Czumaj, Christian Sohler |
| 2002 | Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows. | Mary Cryan, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Russell A. Martin |
| 2002 | Static Optimality Theorem for External Memory String Access. | Valentina Ciriani, Paolo Ferragina, Fabrizio Luccio, S. Muthukrishnan |
| 2002 | Covering Problems with Hard Capacities. | Julia Chuzhoy, Joseph Naor |
| 2002 | Dimension Reduction in the \ell _1 Norm. | Moses Charikar, Amit Sahai |