| 2002 | Kolmogorov's Structure Functions with an Application to the Foundations of Model Selection. | Nikolai K. Vereshchagin, Paul M. B. Vitnyi |
| 2002 | Optimal System of Loops on an Orientable Surface. | ric Colin de Verdire, Francis Lazarus |
| 2002 | A Spectral Algorithm for Learning Mixtures of Distributions. | Santosh S. Vempala, Grant Wang |
| 2002 | On Approximating the Radii of Point Sets in High Dimensions. | Kasturi R. Varadarajan, Srinivasan Venkatesh, Jiawei Zhang |
| 2002 | Randomness Extractors and their Many Guises. | Salil P. Vadhan |
| 2002 | Equivalence between Priority Queues and Sorting. | Mikkel Thorup |
| 2002 | Quantum Lower Bounds for the Collision and the Element Distinctness Problems. | Yaoyun Shi |
| 2002 | A Switching Lemma for Small Restrictions and Lower Bounds for k - DNF Resolution. | Nathan Segerlind, Samuel R. Buss, Russell Impagliazzo |
| 2002 | On the Hardness of Optimal Auctions. | Amir Ronen, Amin Saberi |
| 2002 | Improved Dynamic Reachability Algorithms for Directed Graphs. | Liam Roditty, Uri Zwick |
| 2002 | Quantum Computation and Lattice Problems. | Oded Regev |
| 2002 | Minimizing Congestion in General Networks. | Harald Rcke |
| 2002 | Concurrent Zero Knowledge with Logarithmic Round-Complexity. | Manoj Prabhakaran, Alon Rosen, Amit Sahai |
| 2002 | An Inverse-Ackermann Style Lower Bound for the Online Minimum Spanning Tree. | Seth Pettie |
| 2002 | Load Balancing with Memory. | Michael Mitzenmacher, Balaji Prabhakar, Devavrat Shah |
| 2002 | Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions. | Daniele Micciancio |
| 2002 | LT Codes. | Michael Luby |
| 2002 | Forbidden Information. | Leonid A. Levin |
| 2002 | A Constant-Factor Approximation Algorithm for the Multicommodity Rent-or-Buy Problem. | Amit Kumar, Anupam Gupta, Tim Roughgarden |
| 2002 | Deterministic Broadcasting Time in Radio Networks of Unknown Topology. | Dariusz R. Kowalski, Andrzej Pelc |
| 2002 | The Partition Technique for Overlays of Envelopes. | Vladlen Koltun, Micha Sharir |
| 2002 | Learning Intersections and Thresholds of Halfspaces. | Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio |
| 2002 | Hardness Results for Coloring 3 -Colorable 3 -Uniform Hypergraphs. | Subhash Khot |
| 2002 | Protocols and Impossibility Results for Gossip-Based Communication Mechanisms. | David Kempe, Jon M. Kleinberg |
| 2002 | Spectral Gap and log-Sobolev Constant for Balanced Matroids. | Mark Jerrum, Jung-Bae Son |