| 2002 | 2-round zero knowledge and proof auditors. Cynthia Dwork, Larry J. Stockmeyer |
| 2002 | 3-manifold knot genus is NP-complet. Ian Agol, Joel Hass, William P. Thurston |
| 2002 | A new average case analysis for completion time scheduling. Mark Scharbrodt, Thomas Schickinger, Angelika Steger |
| 2002 | A new greedy approach for facility location problems. Kamal Jain, Mohammad Mahdian, Amin Saberi |
| 2002 | A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant. Mary Cryan, Martin E. Dyer |
| 2002 | A unified analysis of hot video schedulers. Wun-Tat Chan, Tak Wah Lam, Hing-Fung Ting, Prudence W. H. Wong |
| 2002 | Algorithmic derandomization via complexity theory. D. Sivakumar |
| 2002 | Almost all graphs with average degree 4 are 3-colorable. Dimitris Achlioptas, Cristopher Moore |
| 2002 | An exponential separation between regular and general resolution. Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart |
| 2002 | Approximate clustering via core-sets. Mihai Badoiu, Sariel Har-Peled, Piotr Indyk |
| 2002 | Approximate counting of inversions in a data stream. Miklós Ajtai, T. S. Jayram, Ravi Kumar, D. Sivakumar |
| 2002 | Approximating the smallest grammar: Kolmogorov complexity in natural models. Moses Charikar, Eric Lehman, Ding Liu, Rina Panigrahy, Manoj Prabhakaran, April Rasala, Amit Sahai, Abhi Shelat |
| 2002 | Approximation algorithms for minimum-cost k-vertex connected subgraphs. Joseph Cheriyan, Santosh S. Vempala, Adrian Vetta |
| 2002 | Approximation schemes for preemptive weighted flow time. Chandra Chekuri, Sanjeev Khanna |
| 2002 | Average case analysis for batched disk scheduling and increasing subsequences. Eitan Bachmat |
| 2002 | Cache-oblivious priority queue and graph algorithm applications. Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro |
| 2002 | Clairvoyant scheduling of random walks. Péter Gács |
| 2002 | Clifford algebras and approximating the permanent. Steve Chien, Lars Eilstrup Rasmussen, Alistair Sinclair |
| 2002 | Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. Michael Elkin, Guy Kortsarz |
| 2002 | Combinatorial optimization problems in self-assembly. Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo Moisset de Espanés, Paul W. K. Rothemund |
| 2002 | Competitive generalized auctions. Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin |
| 2002 | Competitive recommendation systems. Petros Drineas, Iordanis Kerenidis, Prabhakar Raghavan |
| 2002 | Computing the betti numbers of arrangements. Saugata Basu |
| 2002 | Concurrent zero-knowledge with timing, revisited. Oded Goldreich |
| 2002 | Crawling on web graphs. Colin Cooper, Alan M. Frieze |
| 2002 | Deterministic sorting in O(nlog log n) time and linear space. Yijie Han |
| 2002 | Dynamic subgraph connectivity with geometric applications. Timothy M. Chan |
| 2002 | Equitable cost allocations via primal-dual-type algorithms. Kamal Jain, Vijay V. Vazirani |
| 2002 | Exact learning of DNF formulas using DNF hypotheses. Lisa Hellerstein, Vijay Raghavan |
| 2002 | Expanders from symmetric codes. Roy Meshulam, Avi Wigderson |
| 2002 | Fast, small-space algorithms for approximate histogram maintenance. Anna C. Gilbert, Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan, Martin Strauss |
| 2002 | Finding nearest neighbors in growth-restricted metrics. David R. Karger, Matthias Ruhl |
| 2002 | Fitting algebraic curves to noisy data. Sanjeev Arora, Subhash Khot |
| 2002 | Girth and euclidean distortion. Nathan Linial, Avner Magen, Assaf Naor |
| 2002 | Hard examples for bounded depth frege. Eli Ben-Sasson |
| 2002 | Hardness amplification within NP. Ryan O'Donnell |
| 2002 | Hardness results for approximate hypergraph coloring. Subhash Khot |
| 2002 | Huffman coding with unequal letter costs. Mordecai J. Golin, Claire Kenyon, Neal E. Young |
| 2002 | Improved cryptographic hash functions with worst-case/average-case connection. Daniele Micciancio |
| 2002 | Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. Surender Baswana, Ramesh Hariharan, Sandeep Sen |
| 2002 | Learnability beyond AC0. Jeffrey C. Jackson, Adam R. Klivans, Rocco A. Servedio |
| 2002 | Limits to list decodability of linear codes. Venkatesan Guruswami |
| 2002 | Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines. Spyros C. Kontogiannis |
| 2002 | Meldable heaps and boolean union-find. Haim Kaplan, Nira Shafrir, Robert Endre Tarjan |
| 2002 | Models and thresholds for random constraint satisfaction problems. Michael Molloy |
| 2002 | Monotonicity testing over general poset domains. Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky |
| 2002 | Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. Venkatesan Guruswami, Piotr Indyk |
| 2002 | Near-optimal sparse fourier representations via sampling. Anna C. Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss |
| 2002 | New results on monotone dualization and generating hypergraph transversals. Thomas Eiter, Georg Gottlob, Kazuhisa Makino |
| 2002 | On communication over an entanglement-assisted quantum channel. Ashwin Nayak, Julia Salzman |
| 2002 | On paging with locality of reference. Susanne Albers, Lene M. Favrholdt, Oliver Giel |
| 2002 | On randomized online scheduling. Susanne Albers |
| 2002 | On the advantage over a random assignment. Johan Håstad, Srinivasan Venkatesh |
| 2002 | On the complexity of equilibria. Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra |
| 2002 | On the complexity of matrix product. Ran Raz |
| 2002 | On the composition of authenticated byzantine agreement. Yehuda Lindell, Anna Lysyanskaya, Tal Rabin |
| 2002 | On the power of unique 2-prover 1-round games. Subhash Khot |
| 2002 | Optimal finger search trees in the pointer machine. Gerth Stølting Brodal, George Lagogiannis, Christos Makris, Athanasios K. Tsakalidis, Kostas Tsichlas |
| 2002 | Optimal rate-based scheduling on multiprocessors. Anand Srinivasan, James H. Anderson |
| 2002 | Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. Sean Hallgren |
| 2002 | Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada John H. Reif |
| 2002 | Pseudo-random generators for all hardnesses. Christopher Umans |
| 2002 | Quantum lower bound for the collision problem. Scott Aaronson |
| 2002 | Random sampling and approximation of MAX-CSP problems. Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski |
| 2002 | Random sampling in residual graphs. David R. Karger, Matthew S. Levine |
| 2002 | Randomness conductors and constant-degree lossless expanders. Michael R. Capalbo, Omer Reingold, Salil P. Vadhan, Avi Wigderson |
| 2002 | Recognizing string graphs in NP. Marcus Schaefer, Eric Sedgwick, Daniel Stefankovic |
| 2002 | Reimer's inequality and tardos' conjecture. Clifford D. Smyth |
| 2002 | Relations between average case complexity and approximation complexity. Uriel Feige |
| 2002 | Resolution lower bounds for the weak pigeonhole principle. Ran Raz |
| 2002 | Secure multi-party quantum computation. Claude Crépeau, Daniel Gottesman, Adam D. Smith |
| 2002 | Selfish traffic allocation for server farms. Artur Czumaj, Piotr Krysta, Berthold Vöcking |
| 2002 | Similarity estimation techniques from rounding algorithms. Moses Charikar |
| 2002 | Size space tradeoffs for resolution. Eli Ben-Sasson |
| 2002 | Solving convex programs by random walks. Dimitris Bertsimas, Santosh S. Vempala |
| 2002 | Space lower bounds for distance approximation in the data stream model. Michael E. Saks, Xiaodong Sun |
| 2002 | Space-efficient approximate Voronoi diagrams. Sunil Arya, Theocharis Malamatos, David M. Mount |
| 2002 | Stability of load balancing algorithms in dynamic adversarial systems. Elliot Anshelevich, David Kempe, Jon M. Kleinberg |
| 2002 | Strict polynomial-time in simulation and extraction. Boaz Barak, Yehuda Lindell |
| 2002 | The Glauber dynamics on colourings of a graph with high girth and maximum degree. Michael Molloy |
| 2002 | The Joy of Theory. Christos H. Papadimitriou |
| 2002 | The complexity of approximating entropy. Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, Ronitt Rubinfeld |
| 2002 | The complexity of choosing an H-colouring (nearly) uniformly at random. Leslie Ann Goldberg, Steven Kelk, Mike Paterson |
| 2002 | The importance of being biased. Irit Dinur, Shmuel Safra |
| 2002 | The invasiveness of off-line memory checking. Miklós Ajtai |
| 2002 | The price of anarchy is independent of the network topology. Tim Roughgarden |
| 2002 | Tight security proofs for the bounded-storage model. Stefan Dziembowski, Ueli M. Maurer |
| 2002 | Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems. Paul Beame, Erik Vee |
| 2002 | Tradeoffs in probabilistic packet marking for IP traceback. Micah Adler |
| 2002 | Universally composable two-party and multi-party secure computation. Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, Amit Sahai |
| 2002 | Verifying candidate matches in sparse and wildcard matching. Richard Cole, Ramesh Hariharan |
| 2002 | Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilon. Jonas Holmerin |
| 2002 | Wait-free consensus with infinite arrivals. James Aspnes, Gauri Shah, Jatin Shah |