| 2001 | Recognizing More Unsatisfiable Random 3-SAT Instances Efficiently. | Joel Friedman, Andreas Goerdt |
| 2001 | Routing in Trees. | Pierre Fraigniaud, Cyril Gavoille |
| 2001 | Hidden Pattern Statistics. | Philippe Flajolet, Yves Guivarc'h, Wojciech Szpankowski, Brigitte Valle |
| 2001 | On Minimizing Average Weighted Completion Time of Multiprocessor Tasks with Release Dates. | Aleksei V. Fishkin, Klaus Jansen, Lorant Porkolab |
| 2001 | Combinatorics of Three-Interval Exchanges. | Sbastien Ferenczi, Charles Holton, Luca Q. Zamboni |
| 2001 | Secure Multiparty Computation of Approximations. | Joan Feigenbaum, Yuval Ishai, Tal Malkin, Kobbi Nissim, Martin Strauss, Rebecca N. Wright |
| 2001 | The RPR | Uriel Feige, Michael Langberg |
| 2001 | Fair Simulation Relations, Parity Games, and State Space Reduction for Bchi Automata. | Kousha Etessami, Thomas Wilke, Rebecca A. Schuller |
| 2001 | Approximation Hardness of TSP with Bounded Metrics. | Lars Engebretsen, Marek Karpinski |
| 2001 | Rational Transformations of Formal Power Series. | Manfred Droste, Guo-Qiang Zhang |
| 2001 | New Imperfect Random Source with Applications to Coin-Flipping. | Yevgeniy Dodis |
| 2001 | Solvability of Equations in Free Partially Commutative Groups Is Decidable. | Volker Diekert, Anca Muscholl |
| 2001 | Finite-State Dimension. | Jack Jie Dai, James I. Lathrop, Jack H. Lutz, Elvira Mayordomo |
| 2001 | Testing Hypergraph Coloring. | Artur Czumaj, Christian Sohler |
| 2001 | Permutation Editing and Matching via Embeddings. | Graham Cormode, S. Muthukrishnan, Sleyman Cenk Sahinalp |
| 2001 | Tree Automata with One Memory, Set Constraints, and Ping-Pong Protocols. | Hubert Comon, Vronique Cortier, John Mitchell |
| 2001 | Performance Aspects of Distributed Caches Using TTL-Based Consistency. | Edith Cohen, Eran Halperin, Haim Kaplan |
| 2001 | The Buffer Minimization Problem for Multiprocessor Scheduling with Conflicts. | Marek Chrobak, Jnos Csirik, Csand Imreh, John Noga, Jir Sgall, Gerhard J. Woeginger |
| 2001 | A PTAS for Minimizing Weighted Completion Time on Uniformly Related Machines. | Chandra Chekuri, Sanjeev Khanna |
| 2001 | Approximating the Minimum Spanning Tree Weight in Sublinear Time. | Bernard Chazelle, Ronitt Rubinfeld, Luca Trevisan |
| 2001 | Improved Lower Bounds on the Randomized Complexity of Graph Properties. | Amit Chakrabarti, Subhash Khot |
| 2001 | Fractional Path Coloring with Applications to WDM Networks. | Ioannis Caragiannis, Afonso Ferreira, Christos Kaklamanis, Stephane Perennes, Herv Rivano |
| 2001 | Subexponential Parameterized Algorithms Collapse the W-Hierarchy. | Liming Cai, David W. Juedes |
| 2001 | Time and Space Bounds for Reversible Simulation. | Harry Buhrman, John Tromp, Paul M. B. Vitnyi |
| 2001 | The Complexity of Constructing Evolutionary Trees Using Experiments. | Gerth Stlting Brodal, Rolf Fagerberg, Christian N. S. Pedersen, Anna stlin |