| 2000 | Introduction: The Fourth International Workshop on Randomization and Approximation Techniques in Computer Science. | Andrei Z. Broder |
| 2000 | Min-wise Independent Permutations: Theory and Practice. | Andrei Z. Broder |
| 2000 | A Complete Axiomatization for Observational Congruence of Prioritized Finite-State Behaviors. | Mario Bravetti, Roberto Gorrieri |
| 2000 | A Matrix-based Method for Analysing Stochastic Process Algebras. | Jeremy T. Bradley, N. J. Davies |
| 2000 | On the Representation of Timed Polyhedra. | Olivier Bournez, Oded Maler |
| 2000 | Generating Partial and Multiple Transversals of a Hypergraph. | Endre Boros, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino |
| 2000 | A Note on Parallel Read Operations on Large Public Databases. | Gian Carlo Bongiovanni, Andrea E. F. Clementi, Paolo Penna |
| 2000 | Asymptotically Optimal Bounds for OBDDs and the Solution of Some Basic OBDD Problems. | Beate Bollig, Ingo Wegener |
| 2000 | Closest Vectors, Successive Minima, and Dual HKZ-Bases of Lattices. | Johannes Blmer |
| 2000 | Integrating Two Towers and GreatSPN. | Marco Bernardo, Nadia Busi, Marina Ribaudo |
| 2000 | Testing Acyclicity of Directed Graphs in Sublinear Time. | Michael A. Bender, Dana Ron |
| 2000 | Determinization of Transducers over Infinite Words. | Marie-Pierre Bal, Olivier Carton |
| 2000 | Round-Optimal and Abuse Free Optimistic Multi-party Contract Signing. | Birgit Baum-Waidner, Michael Waidner |
| 2000 | Extended Notions of Security for Multicast Public Key Cryptosystems. | Olivier Baudron, David Pointcheval, Jacques Stern |
| 2000 | Planar Maps and Airy Phenomena. | Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Michle Soria |
| 2000 | Unlearning Helps. | Ganesh R. Baliga, John Case, Wolfgang Merkle, Frank Stephan |
| 2000 | On the Logical Characterisation of Performability Properties. | Christel Baier, Boudewijn R. Haverkort, Holger Hermanns, Joost-Pieter Katoen |
| 2000 | Performance Analysis of UMTS Resource Allocation Strategies using TIPPtool. | Fulvio Babich, Lia Deotto |
| 2000 | Monotone Proofs of the Pigeon Hole Principle. | Albert Atserias, Nicola Galesi, Ricard Gavald |
| 2000 | Experimental Evaluation of Approximation Algorithms for the Minimum Cost Multiple-source Unsplittable Flow Problem. | Yasuhito Asano |
| 2000 | Optimal Projective Algorithms for the List Update Problem. | Christoph Ambhl, Bernd Grtner, Bernhard von Stengel |
| 2000 | Routing Tree Problems on Random Graphs. | Carme lvarez, Rafel Cases, Josep Daz, Jordi Petit, Maria J. Serna |
| 2000 | Improved Algorithms for Finding Level Ancestors in Dynamic Trees. | Stephen Alstrup, Jacob Holm |
| 2000 | Scalable Secure Storage when Half the System Is Faulty. | Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien P. Stern |
| 2000 | An Asynchronous Calculus for Generative-Reactive Probalistic Systems. | Alessandro Aldini, Mario Bravetti |