| 2002 | Optimal rate-based scheduling on multiprocessors. | Anand Srinivasan, James H. Anderson |
| 2002 | Reimer's inequality and tardos' conjecture. | Clifford D. Smyth |
| 2002 | Algorithmic derandomization via complexity theory. | D. Sivakumar |
| 2002 | A new average case analysis for completion time scheduling. | Mark Scharbrodt, Thomas Schickinger, Angelika Steger |
| 2002 | Recognizing string graphs in NP. | Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic |
| 2002 | Space lower bounds for distance approximation in the data stream model. | Michael E. Saks, Xiaodong Sun |
| 2002 | The price of anarchy is independent of the network topology. | Tim Roughgarden |
| 2002 | Resolution lower bounds for the weak pigeonhole principle. | Ran Raz |
| 2002 | On the complexity of matrix product. | Ran Raz |
| 2002 | The Joy of Theory. | Christos H. Papadimitriou |
| 2002 | Hardness amplification within NP. | Ryan O'Donnell |
| 2002 | On communication over an entanglement-assisted quantum channel. | Ashwin Nayak, Julia Salzman |
| 2002 | Models and thresholds for random constraint satisfaction problems. | Michael Molloy |
| 2002 | The Glauber dynamics on colourings of a graph with high girth and maximum degree. | Michael Molloy |
| 2002 | Improved cryptographic hash functions with worst-case/average-case connection. | Daniele Micciancio |
| 2002 | Expanders from symmetric codes. | Roy Meshulam, Avi Wigderson |
| 2002 | Girth and euclidean distortion. | Nathan Linial, Avner Magen, Assaf Naor |
| 2002 | On the composition of authenticated byzantine agreement. | Yehuda Lindell, Anna Lysyanskaya, Tal Rabin |
| 2002 | Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines. | Spyros C. Kontogiannis |
| 2002 | On the power of unique 2-prover 1-round games. | Subhash Khot |
| 2002 | Hardness results for approximate hypergraph coloring. | Subhash Khot |
| 2002 | Finding nearest neighbors in growth-restricted metrics. | David R. Karger, Matthias Ruhl |
| 2002 | Random sampling in residual graphs. | David R. Karger, Matthew S. Levine |
| 2002 | Meldable heaps and boolean union-find. | Haim Kaplan, Nira Shafrir, Robert Endre Tarjan |
| 2002 | Equitable cost allocations via primal-dual-type algorithms. | Kamal Jain, Vijay V. Vazirani |