| 2001 | Majority Consensus and the Local Majority Rule. | Nabil H. Mustafa, Aleksandar Sasa Pekec |
| 2001 | From Finite State Communication Protocols to High-Level Message Sequence Charts. | Anca Muscholl, Doron A. Peled |
| 2001 | Decidable Properties of Graphs of All-Optical Networks. | Luciano Margara, Janos Simon |
| 2001 | A Set-Theoretic Framework for Assume-Guarantee Reasoning. | Patrick Maier |
| 2001 | Distributed Controller Synthesis for Local Specifications. | P. Madhusudan, P. S. Thiagarajan |
| 2001 | Reasoning about Sequential and Branching Behaviours of Message Sequence Graphs. | P. Madhusudan |
| 2001 | The Longest Common Subsequence Problem for Sequences with Nested Arc Annotations. | Guo-Hui Lin, Zhi-Zhong Chen, Tao Jiang, Jianjun Wen |
| 2001 | Efficient Generation of Plane Triangulations without Repetitions. | Zhangjian Li, Shin-Ichi Nakano |
| 2001 | The Trace Coding Problem Is Undecidable. | Michal Kunc |
| 2001 | Knuth-Bendix Constraint Solving Is NP-Complete. | Konstantin Korovin, Andrei Voronkov |
| 2001 | The Star Problem in Trace Monoids: Reductions Beyond C4. | Daniel Kirsten |
| 2001 | Secure Games with Polynomial Expressions. | Aggelos Kiayias, Moti Yung |
| 2001 | Communication Gap for Finite Memory Devices. | Tomasz Jurdzinski, Miroslaw Kutylowski |
| 2001 | Total Colorings of Degenerated Graphs. | Shuji Isobe, Xiao Zhou, Takao Nishizeki |
| 2001 | Quantum Complexities of Ordered Searching, Sorting, and Element Distinctness. | Peter Hyer, Jan Neerbek, Yaoyun Shi |
| 2001 | An Axiomatic Approach to Metareasoning on Nominal Algebras in HOAS. | Furio Honsell, Marino Miculan, Ivan Scagnetto |
| 2001 | Division Is in Uniform TC | William Hesse |
| 2001 | The Complexity of Computing the Size of an Interval. | Lane A. Hemaspaandra, Sven Kosub, Klaus W. Wagner |
| 2001 | Online Packet Routing on Linear Arrays and Rings. | Jessen T. Havill |
| 2001 | Decision Questions Concerning Semilinearity, Morphisms, and Commutation of Languages. | Tero Harju, Oscar H. Ibarra, Juhani Karhumki, Arto Salomaa |
| 2001 | Integrating Semantics for Object-Oriented System Models. | Martin Groe-Rhode |
| 2001 | Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width. | Georg Gottlob, Reinhard Pichler |
| 2001 | On Interactive Proofs with a Laconic Prover. | Oded Goldreich, Salil P. Vadhan, Avi Wigderson |
| 2001 | Approximation Algorithms for Partial Covering Problems. | Rajiv Gandhi, Samir Khuller, Aravind Srinivasan |
| 2001 | Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations. | Martin Frer |