| 2005 | A Gentle Introduction to Semantic Subtyping. | Giuseppe Castagna, Alain Frisch |
| 2005 | On the Hardness of Embeddings Between Two Finite Metrics. | |
| 2005 | Cache-Aware and Cache-Oblivious Adaptive Sorting. | Gerth Stlting Brodal, Rolf Fagerberg, Gabriel Moruz |
| 2005 | An Accessible Approach to Behavioural Pseudometrics. | Franck van Breugel, Claudio Hermida, Michael Makkai, James Worrell |
| 2005 | Classification of Boolean Functions of 6 Variables or Less with Respect to Some Cryptographic Properties. | An Braeken, Yuri L. Borissov, Svetla Nikova, Bart Preneel |
| 2005 | The Polyranking Principle. | Aaron R. Bradley, Zohar Manna, Henny B. Sipma |
| 2005 | How Well Can Primal-Dual and Local-Ratio Algorithms Perform?. | Allan Borodin, David Cashman, Avner Magen |
| 2005 | The Tree Inclusion Problem: In Optimal Space and Faster. | Philip Bille, Inge Li Grtz |
| 2005 | Dynamic Diffusion Load Balancing. | Petra Berenbrink, Tom Friedetzky, Russell A. Martin |
| 2005 | Groupoids That Recognize Only Regular Languages. | Martin Beaudry, Franois Lemieux, Denis Thrien |
| 2005 | Lower Bounds for Lovsz-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. | Paul Beame, Toniann Pitassi, Nathan Segerlind |
| 2005 | On the Equivalence of -Automata. | Marie-Pierre Bal, Sylvain Lombardy, Jacques Sakarovitch |
| 2005 | Computationally Sound Implementations of Equational Theories Against Passive Adversaries. | Mathieu Baudet, Vronique Cortier, Steve Kremer |
| 2005 | A Fully Abstract Encoding of the | Michael Baldamus, Joachim Parrow, Bjrn Victor |
| 2005 | Petri Algebras. | ric Badouel, Jules Chenou, Goulven Guillou |
| 2005 | Facility Location in Sublinear Time. | Mihai Badoiu, Artur Czumaj, Piotr Indyk, Christian Sohler |
| 2005 | On the Cover Time of Random Geometric Graphs. | Chen Avin, Gunes Ercal |
| 2005 | Preservation Under Extensions on Well-Behaved Finite Structures. | Albert Atserias, Anuj Dawar, Martin Grohe |
| 2005 | Noisy Turing Machines. | Eugene Asarin, Pieter Collins |
| 2005 | An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks. | Christoph Ambhl |
| 2005 | Congruences for Visibly Pushdown Languages. | Rajeev Alur, Viraj Kumar, P. Madhusudan, Mahesh Viswanathan |
| 2005 | Union-Find with Constant Time Deletions. | Stephen Alstrup, Inge Li Grtz, Theis Rauhe, Mikkel Thorup, Uri Zwick |
| 2005 | Decidability and Complexity Results for Timed Automata via Channel Machines. | Parosh Aziz Abdulla, Johann Deneux, Jol Ouaknine, James Worrell |
| 2005 | Password-Based Encryption Analyzed. | Martn Abadi, Bogdan Warinschi |
| 2004 | On the Power of Ambainis's Lower Bounds. | Shengyu Zhang |