| 2001 | On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs. | Andrea E. F. Clementi, Pierluigi Crescenzi, Paolo Penna, Gianluca Rossi, Paola Vocca |
| 2001 | Evasiveness of Subgraph Containment and Related Properties. | Amit Chakrabarti, Subhash Khot, Yaoyun Shi |
| 2001 | Recurrence in Infinite Words. | Julien Cassaigne |
| 2001 | A (5/2)n | Markus Blser |
| 2001 | Star-Free Open Languages and Aperiodic Loops. | Martin Beaudry, Franois Lemieux, Denis Thrien |
| 2001 | On the Class of Languages Recognizable by 1-Way Quantum Finite Automata. | Andris Ambainis, Arnolds Kikusts, Maris Valdats |
| 2001 | Matching Polygonal Curves with Respect to the Frchet Distance. | Helmut Alt, Christian Knauer, Carola Wenk |
| 2001 | On the Difference between Polynomial-Time Many-One and Truth-Table Reducibilities on Distributional Problems. | Shin Aida, Rainer Schuler, Tatsuie Tsukiji, Osamu Watanabe |
| 2001 | 2-Nested Simulation Is Not Finitely Equationally Axiomatizable. | Luca Aceto, Wan J. Fokkink, Anna Inglfsdttir |
| 2000 | Codes and Graphs. | Mohammad Amin Shokrollahi |
| 2000 | The Data Broadcast Problem with Preemption. | Nicolas Schabanel |
| 2000 | About Cube-Free Morphisms. | Gwnal Richomme, Francis Wlazinski |
| 2000 | Succinct Representations of Model Based Belief Revision. | Paolo Penna |
| 2000 | Multi-linearity Self-Testing with Relative Error. | Frdric Magniez |
| 2000 | Bias Invariance of Small Upper Spans. | Jack H. Lutz, Martin Strauss |
| 2000 | Hard Instances of Hard Problems. | Jack H. Lutz, Vikram Mhetre, Sridhar Srinivasan |
| 2000 | Controlled Conspiracy-2 Search. | Ulf Lorenz |
| 2000 | Logics Capturing Local Properties. | Leonid Libkin |
| 2000 | Pruning Graphs with Digital Search Trees. Application to Distance Hereditary Graphs. | Jean-Marc Lanlignel, Olivier Raynaud, Eric Thierry |
| 2000 | The CNN Problem and Other k-Server Variants. | Elias Koutsoupias, David Scot Taylor |
| 2000 | The Boolean Hierarchy of NP-Partitions. | Sven Kosub, Klaus W. Wagner |
| 2000 | Circuits versus Trees in Algebraic Complexity. | Pascal Koiran |
| 2000 | Distance Labeling Schemes for Well-Separated Graph Classes. | Michal Katz, Nir A. Katz, David Peleg |
| 2000 | Linear Cellular Automata with Multiple State Variables. | Jarkko Kari |
| 2000 | Hereditary History Preserving Bisimilarity Is Undecidable. | Marcin Jurdzinski, Mogens Nielsen |