| 2001 | New Results on Alternating and Non-deterministic Two-Dimensional Finite-State Automata. | Jarkko Kari, Cristopher Moore |
| 2001 | A Simple Undecidable Problem: The Inclusion Problem for Finite Substitutions on ab | Juhani Karhumki, Leonid P. Lisovik |
| 2001 | Refining the Hierarchy of Blind Multicounter Languages. | Matthias Jantzen, Alexy Kurganskyy |
| 2001 | Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs. | Klaus Jansen, Marek Karpinski, Andrzej Lingas, Eike Seidel |
| 2001 | A Toolkit for First Order Extensions of Monadic Games. | David Janin, Jerzy Marcinkowski |
| 2001 | Space Efficient Algorithms for Series-Parallel Graphs. | Andreas Jakoby, Maciej Liskiewicz, Rdiger Reischuk |
| 2001 | Small PCPs with Low Query Complexity. | Prahladh Harsha, Madhu Sudan |
| 2001 | Efficient Minimal Perfect Hashing in Nearly Minimal Space. | Torben Hagerup, Torsten Tholey |
| 2001 | Generalized Model-Checking Problems for First-Order Logic. | Martin Grohe |
| 2001 | On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages. | Massimiliano Goldwurm, Beatrice Palano, Massimo Santini |
| 2001 | Efficient Recognition of Random Unsatisfiable k-SAT Instances by Spectral Methods. | Andreas Goerdt, Michael Krivelevich |
| 2001 | Learning Expressions over Monoids. | Ricard Gavald, Denis Thrien |
| 2001 | Optimal and Approximate Station Placement in Networks (With Applications to Multicasting and Space Efficient Traversals). | Clemente Galdi, Christos Kaklamanis, Manuela Montangero, Pino Persiano |
| 2001 | Generalized Langton's Ant: Dynamical Behavior and Complexity. | Anah Gajardo, Eric Goles Ch., Andrs Moreira |
| 2001 | Gathering of Asynchronous Oblivious Robots with Limited Visibility. | Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, Peter Widmayer |
| 2001 | The UPS Problem. | Cristina G. Fernandes, Till Nierhoff |
| 2001 | Optimal Preemptive Scheduling on Uniform Processors with Non-decreasing Speed Ratios. | Leah Epstein |
| 2001 | Scalable Sparse Topologies with Small Spectrum. | Robert Elssser, Rastislav Kralovic, Burkhard Monien |
| 2001 | On Multipartition Communication Complexity. | Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger |
| 2001 | Randomness, Computability, and Density. | Rodney G. Downey, Denis R. Hirschfeldt, Andr Nies |
| 2001 | Recursive Randomized Coloring Beats Fair Dice Random Colorings. | Benjamin Doerr, Anand Srivastav |
| 2001 | The Existential Theory of Equations with Rational Constraints in Free Groups is PSPACE-Complete. | Volker Diekert, Claudio Gutierrez, Christian Hagenah |
| 2001 | Deterministic Radio Broadcasting at Low Cost. | Anders Dessmark, Andrzej Pelc |
| 2001 | Residual Finite State Automata. | Franois Denis, Aurlien Lemay, Alain Terlutte |
| 2001 | On Presburger Liveness of Discrete Timed Automata. | Zhe Dang, Pierluigi San Pietro, Richard A. Kemmerer |