| 2002 | A new greedy approach for facility location problems. | Kamal Jain, Mohammad Mahdian, Amin Saberi |
| 2002 | Learnability beyond AC0. | Jeffrey C. Jackson, Adam R. Klivans, Rocco A. Servedio |
| 2002 | Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilon. | Jonas Holmerin |
| 2002 | Exact learning of DNF formulas using DNF hypotheses. | Lisa Hellerstein, Vijay Raghavan |
| 2002 | On the advantage over a random assignment. | Johan Hstad, Srinivasan Venkatesh |
| 2002 | Deterministic sorting in O(nlog log n) time and linear space. | Yijie Han |
| 2002 | Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. | Sean Hallgren |
| 2002 | Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. | Venkatesan Guruswami, Piotr Indyk |
| 2002 | Limits to list decodability of linear codes. | Venkatesan Guruswami |
| 2002 | Huffman coding with unequal letter costs. | Mordecai J. Golin, Claire Kenyon, Neal E. Young |
| 2002 | Concurrent zero-knowledge with timing, revisited. | Oded Goldreich |
| 2002 | The complexity of choosing an H-colouring (nearly) uniformly at random. | Leslie Ann Goldberg, Steven Kelk, Mike Paterson |
| 2002 | Near-optimal sparse fourier representations via sampling. | Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss |
| 2002 | Fast, small-space algorithms for approximate histogram maintenance. | Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin Strauss |
| 2002 | Clairvoyant scheduling of random walks. | Pter Gcs |
| 2002 | Monotonicity testing over general poset domains. | Eldar Fischer, Eric P. Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky |
| 2002 | Competitive generalized auctions. | Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin |
| 2002 | Relations between average case complexity and approximation complexity. | Uriel Feige |
| 2002 | Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. | Michael Elkin, Guy Kortsarz |
| 2002 | New results on monotone dualization and generating hypergraph transversals. | Thomas Eiter, Georg Gottlob, Kazuhisa Makino |
| 2002 | Tight security proofs for the bounded-storage model. | Stefan Dziembowski, Ueli M. Maurer |
| 2002 | 2-round zero knowledge and proof auditors. | Cynthia Dwork, Larry J. Stockmeyer |
| 2002 | Competitive recommendation systems. | Petros Drineas, Iordanis Kerenidis, Prabhakar Raghavan |
| 2002 | The importance of being biased. | Irit Dinur, Shmuel Safra |
| 2002 | On the complexity of equilibria. | Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra |