| 2005 | A Lower Bound on the Complexity of Polynomial Multiplication Over Finite Fields. | Michael Kaminski |
| 2005 | Deciding Properties of Contract-Signing Protocols. | Detlef Khler, Ralf Ksters, Thomas Wilke |
| 2005 | Topological Automata. | Emmanuel Jeandel |
| 2005 | Cycle Cover with Short Cycles. | Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni |
| 2005 | On the Computational Complexity of the Forcing Chromatic Number. | Frank Harary, Wolfgang Slany, Oleg Verbitsky |
| 2005 | Quantum Interactive Proofs with Competing Provers. | Gus Gutoski, John Watrous |
| 2005 | Fast Pruning of Geometric Spanners. | Joachim Gudmundsson, Giri Narasimhan, Michiel H. M. Smid |
| 2005 | Minimizing NFA's and Regular Expressions. | Gregor Gramlich, Georg Schnitger |
| 2005 | Pattern Occurrences in Multicomponent Models. | Massimiliano Goldwurm, Violetta Lonati |
| 2005 | Polylog-Time Reductions Decrease Dot-Depth. | Christian Glaer |
| 2005 | Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves. | Gianni Franceschini |
| 2005 | Solving Medium-Density Subset Sum Problems in Expected Polynomial Time. | Abraham Flaxman, Bartosz Przydatek |
| 2005 | Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations. | Kousha Etessami, Mihalis Yannakakis |
| 2005 | More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP. | Lars Engebretsen, Jonas Holmerin |
| 2005 | Three Optimal Algorithms for Balls of Three Colors. | Zdenek Dvork, Vt Jelnek, Daniel Krl, Jan Kyncl, Michael E. Saks |
| 2005 | Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms. | Petros Drineas, Ravi Kannan, Michael W. Mahoney |
| 2005 | Roundings Respecting Hard Constraints. | Benjamin Doerr |
| 2005 | Connectivity for Wireless Agents Moving on a Cycle or Grid. | Josep Daz, Xavier Prez-Gimnez, Maria J. Serna, Nicholas C. Wormald |
| 2005 | Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size. | Jianer Chen, Henning Fernau, Iyad A. Kanj, Ge Xia |
| 2005 | Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms. | Hubie Chen |
| 2005 | The PIGs Full Monty - A Floor Show of Minimal Separators. | Gerard Jennhwa Chang, Ton Kloks, Jiping Liu, Sheng-Lung Peng |
| 2005 | Varieties of Codes and Kraft Inequality. | Fabio Burderi, Antonio Restivo |
| 2005 | Robust Polynomials and Quantum Algorithms. | Harry Buhrman, Ilan Newman, Hein Rhrig, Ronald de Wolf |
| 2005 | Increasing Kolmogorov Complexity. | Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin |
| 2005 | On the Decidability of Temporal Properties of Probabilistic Pushdown Automata. | Toms Brzdil, Antonn Kucera, Oldrich Strazovsk |