| 2002 | Removable Online Knapsack Problems. | Kazuo Iwama, Shiro Taketomi |
| 2002 | Perfect Constant-Round Secure Computation via Perfect Randomizing Polynomials. | Yuval Ishai, Eyal Kushilevitz |
| 2002 | Bounded-Depth Frege Systems with Counting Axioms Polynomially Simulate Nullstellensatz Refutations. | Russell Impagliazzo, Nathan Segerlind |
| 2002 | Improved Inapproximability Results for Vertex Cover on k -Uniform Hypergraphs. | Jonas Holmerin |
| 2002 | Why Computational Complexity Requires Stricter Martingales. | John M. Hitchcock, Jack H. Lutz |
| 2002 | Correspondence Principles for Effective Dimensions. | John M. Hitchcock |
| 2002 | A Banach-Mazur Computable But Not Markov Computable Function on the Computable Real Numbers. | Peter Hertling |
| 2002 | Program Debugging and Validation Using Semantic Approximations and Partial Specifications. | Manuel V. Hermenegildo, Germn Puebla, Francisco Bueno, Pedro Lpez-Garca |
| 2002 | Synthesis of Uninitialized Systems. | Thomas A. Henzinger, Sriram C. Krishnan, Orna Kupferman, Freddy Y. C. Mang |
| 2002 | The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications. | Robert A. Hearn, Erik D. Demaine |
| 2002 | Histogramming Data Streams with Fast Per-Item Processing. | Sudipto Guha, Piotr Indyk, S. Muthukrishnan, Martin Strauss |
| 2002 | Exponential Lower Bound for Static Semi-algebraic Proofs. | Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik |
| 2002 | Infinite-State High-Level MSCs: Model-Checking and Realizability. | Blaise Genest, Anca Muscholl, Helmut Seidl, Marc Zeitoun |
| 2002 | An Elementary Expressively Complete Temporal Logic for Mazurkiewicz Traces. | Paul Gastin, Madhavan Mukund |
| 2002 | Spanning Trees with Bounded Number of Branch Vertices. | Luisa Gargano, Pavol Hell, Ladislav Stacho, Ugo Vaccaro |
| 2002 | The Structure and Complexity of Nash Equilibria for a Selfish Routing Game. | Dimitris Fotakis, Spyros C. Kontogiannis, Elias Koutsoupias, Marios Mavronicolas, Paul G. Spirakis |
| 2002 | Seamless Integration of Parallelism and Memory Hierarchy. | Carlo Fantozzi, Andrea Pietracaprina, Geppino Pucci |
| 2002 | Heuristically Optimized Trade-Offs: A New Paradigm for Power Laws in the Internet. | Alex Fabrikant, Elias Koutsoupias, Christos H. Papadimitriou |
| 2002 | On the Complexity of Resolution with Bounded Conjunctions. | Juan Luis Esteban, Nicola Galesi, Jochen Messner |
| 2002 | New Bounds for Variable-Sized and Resource Augmented Online Bin Packing. | Leah Epstein, Steven S. Seiden, Rob van Stee |
| 2002 | Inapproximability Results for Equations over Finite Groups. | Lars Engebretsen, Jonas Holmerin, Alexander Russell |
| 2002 | Priority Queues, Pairing, and Adaptive Sorting. | Amr Elmasry |
| 2002 | Random Sampling from Boltzmann Principles. | Philippe Duchon, Philippe Flajolet, Guy Louchard, Gilles Schaeffer |
| 2002 | On the Average Performance of Orthogonal Range Search in Multidimensional Data Structures. | Amalia Duch, Conrado Martnez |
| 2002 | Antirandomizing the Wrong Game. | Benjamin Doerr |