| 2000 | An Optimal Online Algorithm for Bounded Space Variable-Sized Bin Packing. | Steven S. Seiden |
| 2000 | Revisiting the Correspondence between Cut Elimination and Normalisation. | Jos Esprito Santo |
| 2000 | Necessary and Sufficient Assumptions for Non-iterative Zero-Knowledge Proofs of Knowledge for All NP Relations. | Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano |
| 2000 | An Intrinsic Semantics of Intersection Types. | John C. Reynolds |
| 2000 | Lax Logical Relations. | Gordon D. Plotkin, John Power, Donald Sannella, Robert D. Tennent |
| 2000 | Negation Elimination from Simple Equational Formulae. | Reinhard Pichler |
| 2000 | Can Graph Grammars Make Formal Methods More Human? | Mauro Pezz, Luciano Baresi |
| 2000 | An Optimal Minimum Spanning Tree Algorithm. | Seth Pettie, Vijaya Ramachandran |
| 2000 | Which Graphs for Visual Modeling? | Francesco Parisi-Presicce |
| 2000 | Dispersing Hash Functions. | Rasmus Pagh |
| 2000 | Rule-Based and Visual Model Evolution using GENGED. | Julia Padberg, Claudia Ermel, Roswitha Bardohl |
| 2000 | Efficient Communication Establishment in Adverse Communication Environments. | Sotiris E. Nikoletseas, Paul G. Spirakis |
| 2000 | On the Power of Tree-Walking Automata. | Frank Neven, Thomas Schwentick |
| 2000 | Wavelength Routing of Uniform Instances in Optical Rings. | Lata Narayanan, Jaroslav Opatrny |
| 2000 | A Statically Allocated Parallel Functional Language. | Alan Mycroft, Richard Sharp |
| 2000 | Generic and Polymorphic Graph Transformations-Supporting the Definition of Visual Languages. | Manfred Mnch, Andy Schrr |
| 2000 | An Automata-Theoretic Completeness Proof for Interval Temporal Logic. | Ben C. Moszkowski |
| 2000 | On the Shannon Function for Partially Defined Boolean Functions. | Peter Bro Miltersen |
| 2000 | What Entailment Can do for Type Theory. | Robert K. Meyer |
| 2000 | The Global Power of Additional Queries to p-Random Oracles. | Wolfgang Merkle |
| 2000 | Constraint Programming and Graph Algorithms. | Kurt Mehlhorn |
| 2000 | Reasoning about Message Passing in Finite State Environments. | B. Meenakshi, Ramaswamy Ramanujam |
| 2000 | The Many Faces of a Translation. | Pierre McKenzie, Thomas Schwentick, Denis Thrien, Heribert Vollmer |
| 2000 | On the Complexity of Bisimulation Problems for Basic Parallel Processes. | Richard Mayr |
| 2000 | Characterizing Strongly Normalizing Terms of a Calculus with Generalized Applications via Intersection Types. | Ralph Matthes |