| 2005 | Generic Density and Small Span Theorem. | Philippe Moser |
| 2005 | Approximation Results for the Weighted P | Jrme Monnot, Sophie Toulouse |
| 2005 | Decidable Membership Problems for Finite Recurrent Systems over Sets of Naturals. | Daniel Meister |
| 2005 | An Explicit Solution to Post's Problem over the Reals. | Klaus Meer, Martin Ziegler |
| 2005 | A Type System for Computationally Secure Information Flow. | Peeter Laud, Varmo Vene |
| 2005 | On the Incompressibility of Monotone DNFs. | Matthias P. Krieger |
| 2005 | On Approximating Real-World Halting Problems. | Sven Khler, Christian Schindelhauer, Martin Ziegler |
| 2005 | Leftist Grammars and the Chomsky Hierarchy. | Tomasz Jurdzinski, Krzysztof Lorys |
| 2005 | Translational Lemmas for Alternating TMs and PRAMs. | Chuzo Iwamoto, Yoshiaki Nakashiba, Kenichi Morita, Katsunobu Imai |
| 2005 | Fully Incremental LCS Computation. | Yusuke Ishida, Shunsuke Inenaga, Ayumi Shinohara, Masayuki Takeda |
| 2005 | Shrinking Multi-pushdown Automata. | Markus Holzer, Friedrich Otto |
| 2005 | Biautomatic Semigroups. | Michael Hoffmann, Richard M. Thomas |
| 2005 | On Finding Acyclic Subhypergraphs. | Kouichi Hirata, Megumi Kuwabara, Masateru Harao |
| 2005 | A New Linearizing Restriction in the Pattern Matching Problem. | Yo-Sub Han, Derick Wood |
| 2005 | Improved Algorithms and Complexity Results for Power Domination in Graphs. | Jiong Guo, Rolf Niedermeier, Daniel Raible |
| 2005 | The Complexity of Querying External Memory and Streaming Data. | Martin Grohe, Christoph Koch, Nicole Schweikardt |
| 2005 | Algorithms for Graphs Embeddable with Few Crossings Per Edge. | Alexander Grigoriev, Hans L. Bodlaender |
| 2005 | Reconstructing Many Partitions Using Spectral Techniques. | Joachim Giesen, Dieter Mitsche |
| 2005 | Simple Stochastic Games and P-Matrix Generalized Linear Complementarity Problems. | Bernd Grtner, Leo Rst |
| 2005 | On the Black-Box Complexity of Sperner's Lemma. | Katalin Friedl, Gbor Ivanyos, Miklos Santha, Yves F. Verhoeven |
| 2005 | Exact Algorithms for Graph Homomorphisms. | Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch |
| 2005 | Bounds on the Power of Constant-Depth Quantum Circuits. | Stephen A. Fenner, Frederic Green, Steven Homer, Yong Zhang |
| 2005 | Deterministic Automata on Unranked Trees. | Julien Cristau, Christof Lding, Wolfgang Thomas |
| 2005 | Almost Optimal Explicit Selectors. | Bogdan S. Chlebus, Dariusz R. Kowalski |
| 2005 | The Complexity of Semilinear Problems in Succinct Representation. | Peter Brgisser, Felipe Cucker, Paulin Jacob de Naurois |