| 2005 | Two Logical Hierarchies of Optimization Problems over the Real Numbers. | Uffe Flarup Hansen, Klaus Meer |
| 2005 | On the Complexity of Mixed Discriminants and Related Problems. | Leonid Gurvits |
| 2005 | Interactive Algorithms 2005. | Yuri Gurevich |
| 2005 | Languages Representable by Vertex-Labeled Graphs. | Igor Grunsky, Oleksiy Kurganskyy, Igor Potapov |
| 2005 | The Expressive Power of Two-Variable Least Fixed-Point Logics. | Martin Grohe, Stephan Kreutzer, Nicole Schweikardt |
| 2005 | Complexity of DNF and Isomorphism of Monotone Formulas. | Judy Goldsmith, Matthias Hagen, Martin Mundhenk |
| 2005 | Canonical Disjoint NP-Pairs of Propositional Proof Systems. | Christian Glaer, Alan L. Selman, Liyu Zhang |
| 2005 | Autoreducibility, Mitoticity, and Immunity. | Christian Glaer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang |
| 2005 | Goals in the Propositional Horn Language Are Monotone Boolean Circuits. | Joxe Gaintzarain, Montserrat Hermo, Marisa Navarro |
| 2005 | Knot Theory, Jones Polynomial and Quantum Computing. | Rusins Freivalds |
| 2005 | Nondeterministic Graph Searching: From Pathwidth to Treewidth. | Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse |
| 2005 | Packing Weighted Rectangles into a Square. | Aleksei V. Fishkin, Olga Gerber, Klaus Jansen, Roberto Solis-Oba |
| 2005 | Matrix and Graph Orders Derived from Locally Constrained Graph Homomorphisms. | Jir Fiala, Danil Paulusma, Jan Arne Telle |
| 2005 | Finding Exact and Maximum Occurrences of Protein Complexes in Protein-Protein Interaction Graphs. | Guillaume Fertin, Romeo Rizzi, Stphane Vialette |
| 2005 | Fully Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata. | Nazim Fats, Michel Morvan, Nicolas Schabanel, Eric Thierry |
| 2005 | Separating the Notions of Self- and Autoreducibility. | Piotr Faliszewski, Mitsunori Ogihara |
| 2005 | Online Interval Coloring with Packing Constraints. | Leah Epstein, Meital Levy |
| 2005 | Zeta-Dimension. | David Doty, Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo, Philippe Moser |
| 2005 | Basis of Solutions for a System of Linear Inequalities in Integers: Computation and Applications. | Dimitri Chubarov, Andrei Voronkov |
| 2005 | Approximating Polygonal Objects by Deformable Smooth Surfaces. | Ho-Lun Cheng, Tony Tan |
| 2005 | New Resource Augmentation Analysis of the Total Stretch of SRPT and SJF in Multiprocessor Scheduling. | Wun-Tat Chan, Tak Wah Lam, Kin-Shing Liu, Prudence W. H. Wong |
| 2005 | Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix. | Ho-Leung Chan, Jesper Jansson, Tak Wah Lam, Siu-Ming Yiu |
| 2005 | A Bridge Between the Asynchronous Message Passing Model and Local Computations in Graphs. | Jrmie Chalopin, Yves Mtivier |
| 2005 | Basic Properties for Sand Automata. | Julien Cervelle, Enrico Formenti, Benot Masson |
| 2005 | Linearly Bounded Infinite Graphs. | Arnaud Carayol, Antoine Meyer |