| 2000 | A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols. Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson |
| 2000 | A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors. Mario Bravetti, Roberto Gorrieri |
| 2000 | A New Unfolding Approach to LTL Model Checking. Javier Esparza, Keijo Heljanko |
| 2000 | A Statically Allocated Parallel Functional Language. Alan Mycroft, Richard Sharp |
| 2000 | Algebraic Models for Contextual Nets. Roberto Bruni, Vladimiro Sassone |
| 2000 | Alternating the Temporal Picture for Safety. Zohar Manna, Henny Sipma |
| 2000 | An Wan J. Fokkink, S. P. Luttik |
| 2000 | An Automata-Theoretic Completeness Proof for Interval Temporal Logic. Ben C. Moszkowski |
| 2000 | An Optimal Minimum Spanning Tree Algorithm. Seth Pettie, Vijaya Ramachandran |
| 2000 | An Optimal Online Algorithm for Bounded Space Variable-Sized Bin Packing. Steven S. Seiden |
| 2000 | Analysing Input/Output-Capabilities of Mobile Processes with a Generic Type System. Barbara König |
| 2000 | Approximate TSP in Graphs with Forbidden Minors. Michelangelo Grigni |
| 2000 | Approximating the Independence Number and the Chromatic Number in Expected Polynominal Time. Michael Krivelevich, Van H. Vu |
| 2000 | Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems. Beate Bollig, Ingo Wegener |
| 2000 | Automata, Languages and Programming, 27th International Colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000, Proceedings Ugo Montanari, José D. P. Rolim, Emo Welzl |
| 2000 | Average Bit-Complexity of Euclidean Algorithms. Ali Akhavi, Brigitte Vallée |
| 2000 | Clique Is Hard to Approximate within Lars Engebretsen, Jonas Holmerin |
| 2000 | Closed Types as a Simple Approach to Safe Imperative Multi-stage Programming. Cristiano Calcagno, Eugenio Moggi, Walid Taha |
| 2000 | Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices. Johannes Blömer |
| 2000 | Computing the Girth of a Planar Graph. Hristo N. Djidjev |
| 2000 | Constraint Programming and Graph Algorithms. Kurt Mehlhorn |
| 2000 | Constraint Satisfaction Problems and Finite Algebras. Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons |
| 2000 | Decidable First-Order Transition Logics for PA-Processes. Denis Lugiez, Philippe Schnoebelen |
| 2000 | Deterministic Algorithms for Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning |
| 2000 | Deterministic Radio Broadcasting. Bogdan S. Chlebus, Leszek Gasieniec, Anna Östlin, John Michael Robson |
| 2000 | Determinization of Transducers over Infinite Words. Marie-Pierre Béal, Olivier Carton |
| 2000 | Efficient Verification Algorithms for One-Counter Processes. Antonín Kucera |
| 2000 | Extended Notions of Security for Multicast Public Key Cryptosystems. Olivier Baudron, David Pointcheval, Jacques Stern |
| 2000 | Fast Approximation Schemes for Euclidean Multi-connectivity Problems. Artur Czumaj, Andrzej Lingas |
| 2000 | Fast Verification of Any Remote Procedure Call: Short Witness-Indistinguishable One-Round Proofs for NP. William Aiello, Sandeep N. Bhatt, Rafail Ostrovsky, Sivaramakrishnan Rajagopalan |
| 2000 | Fully-Abstract Statecharts Semantics via Intuitionistic Kripke Models. Gerald Lüttgen, Michael Mendler |
| 2000 | Gales and the Constructive Dimension of Individual Sequences. Jack H. Lutz |
| 2000 | Game Semantics: Achievements and Prospects. Samson Abramsky |
| 2000 | Generating Partial and Multiple Transversals of a Hypergraph. Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino |
| 2000 | Graph Transformation as a Conceptual and Formal Framework for System Modeling and Model Evolution. Gregor Engels, Reiko Heckel |
| 2000 | Hardness of Set Cover with Intersection 1. V. S. Anil Kumar, Sunil Arya, H. Ramesh |
| 2000 | Homogenization and the Polynominal Calculus. Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi |
| 2000 | Improved Algorithms for Finding Level Ancestors in Dynamic Trees. Stephen Alstrup, Jacob Holm |
| 2000 | Improved Shortest Paths on the Word RAM. Torben Hagerup |
| 2000 | Infinite Series-Parallel Posets: Logic and Languages. Dietrich Kuske |
| 2000 | Information Flow vs. Resource Access in the Asynchronous Pi-Calculus. Matthew Hennessy, James Riely |
| 2000 | LTL Is Expressively Complete for Mazurkiewicz Traces. Volker Diekert, Paul Gastin |
| 2000 | Lax Logical Relations. Gordon D. Plotkin, John Power, Donald Sannella, Robert D. Tennent |
| 2000 | Lower Bounds Are Not Easier over the Reals: Inside PH. Hervé Fournier, Pascal Koiran |
| 2000 | Measures of Nondeterminism in Finite Automata. Juraj Hromkovic, Juhani Karhumäki, Hartmut Klauck, Georg Schnitger, Sebastian Seibert |
| 2000 | Min-wise Independent Permutations: Theory and Practice. Andrei Z. Broder |
| 2000 | Monotone Proofs of the Pigeon Hole Principle. Albert Atserias, Nicola Galesi, Ricard Gavaldà |
| 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 | Negation Elimination from Simple Equational Formulae. Reinhard Pichler |
| 2000 | Non Interference for the Analysis of Cryptographic Protocols. Riccardo Focardi, Roberto Gorrieri, Fabio Martinelli |
| 2000 | On Deciding if Deterministic Rabin Language Is in Büchi Class. Tomasz Fryderyk Urbanski |
| 2000 | On Message Sequence Graphs and Finitely Generated Regular MSC Languages. Jesper G. Henriksen, Madhavan Mukund, K. Narayan Kumar, P. S. Thiagarajan |
| 2000 | On the Centralizer of a Finite Set. Juhani Karhumäki, Ion Petre |
| 2000 | On the Complexity of Bisimulation Problems for Basic Parallel Processes. Richard Mayr |
| 2000 | On the Logical Characterisation of Performability Properties. Christel Baier, Boudewijn R. Haverkort, Holger Hermanns, Joost-Pieter Katoen |
| 2000 | On the Power of Tree-Walking Automata. Frank Neven, Thomas Schwentick |
| 2000 | On the Representation of Timed Polyhedra. Olivier Bournez, Oded Maler |
| 2000 | One-Round Secure Computation and Secure Autonomous Mobile Agents. Christian Cachin, Jan Camenisch, Joe Kilian, Joy Müller |
| 2000 | Optimal Projective Algorithms for the List Update Problem. Christoph Ambühl, Bernd Gärtner, Bernhard von Stengel |
| 2000 | Planar Maps and Airy Phenomena. Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Michèle Soria |
| 2000 | Polynominal Time Approximation Schemes for General Multiprocessor Job Shop Scheduling. Klaus Jansen, Lorant Porkolab |
| 2000 | Pseudorandomness. Oded Goldreich |
| 2000 | Reasoning about Idealized ALGOL Using Regular Languages. Dan R. Ghica, Guy McCusker |
| 2000 | Reasoning about Message Passing in Finite State Environments. B. Meenakshi, Ramaswamy Ramanujam |
| 2000 | Resource Augmentation for Online Bounded Space Bin Packing. János Csirik, Gerhard J. Woeginger |
| 2000 | Revisiting the Correspondence between Cut Elimination and Normalisation. José Espírito Santo |
| 2000 | Round-Optimal and Abuse Free Optimistic Multi-party Contract Signing. Birgit Baum-Waidner, Michael Waidner |
| 2000 | Scalable Secure Storage when Half the System Is Faulty. Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien P. Stern |
| 2000 | Strong Inapproximability of the Basic Michael Elkin, David Peleg |
| 2000 | Testing Acyclicity of Directed Graphs in Sublinear Time. Michael A. Bender, Dana Ron |
| 2000 | The Genomics Revolution and Its Challenges for Algorithmic Research. Richard M. Karp |
| 2000 | The Global Power of Additional Queries to p-Random Oracles. Wolfgang Merkle |
| 2000 | The Many Faces of a Translation. Pierre McKenzie, Thomas Schwentick, Denis Thérien, Heribert Vollmer |
| 2000 | The Measurement Process in Domain Theory. Keye Martin |
| 2000 | Tight Size Bounds for Packet Headers in Narrow Meshes. Micah Adler, Faith E. Fich, Leslie Ann Goldberg, Mike Paterson |
| 2000 | Unlearning Helps. Ganesh R. Baliga, John Case, Wolfgang Merkle, Frank Stephan |
| 2000 | Variable Independence, Quantifier Elimination, and Constraint Representations. Leonid Libkin |
| 2000 | Wavelength Assignment Problem on All-Optical Networks with Luciano Margara, Janos Simon |
| 2000 | Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms? Johan Håstad |