| 2005 | A Lower Bound on the Complexity of Polynomial Multiplication Over Finite Fields. Michael Kaminski |
| 2005 | A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs. Telikepalli Kavitha, Kurt Mehlhorn |
| 2005 | Algebraic Generating Functions in Enumerative Combinatorics and Context-Free Languages. Mireille Bousquet-Mélou |
| 2005 | Algorithmics in Exponential Time. Uwe Schöning |
| 2005 | All-Pairs Nearly 2-Approximate Shortest-Paths in O(n Surender Baswana, Vishrut Goyal, Sandeep Sen |
| 2005 | Approximate Range Mode and Range Median Queries. Prosenjit Bose, Evangelos Kranakis, Pat Morin, Yihui Tang |
| 2005 | Automatic Presentations for Finitely Generated Groups. Graham P. Oliver, Richard M. Thomas |
| 2005 | Automorphisms of Finite Rings and Applications to Complexity of Problems. Manindra Agrawal, Nitin Saxena |
| 2005 | Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods. Victor Poupet |
| 2005 | Centrality Measures Based on Current Flow. Ulrik Brandes, Daniel Fleischer |
| 2005 | Characterizing TC Andreas Krebs, Klaus-Jörn Lange, Stephanie Reifferscheid |
| 2005 | Computing Minimal Multi-homogeneous Bézout Numbers Is Hard. Gregorio Malajovich, Klaus Meer |
| 2005 | Connectivity for Wireless Agents Moving on a Cycle or Grid. Josep Díaz, Xavier Pérez-Giménez, Maria J. Serna, Nicholas C. Wormald |
| 2005 | Cost Sharing and Strategyproof Mechanisms for Set Cover Games. Xiang-Yang Li, Zheng Sun, Weizhao Wang |
| 2005 | Counting in the Two Variable Guarded Logic with Transitivity. Lidia Tendera |
| 2005 | Cycle Cover with Short Cycles. Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni |
| 2005 | Deciding Properties of Contract-Signing Protocols. Detlef Kähler, Ralf Küsters, Thomas Wilke |
| 2005 | Dynamic Complexity Theory Revisited. Volker Weber, Thomas Schwentick |
| 2005 | Exact Quantum Algorithms for the Leader Election Problem. Seiichiro Tani, Hirotada Kobayashi, Keiji Matsumoto |
| 2005 | Fast Pruning of Geometric Spanners. Joachim Gudmundsson, Giri Narasimhan, Michiel H. M. Smid |
| 2005 | How Common Can Be Universality for Cellular Automata?. Guillaume Theyssier |
| 2005 | Improved Algorithms for Dynamic Page Migration. Marcin Bienkowski, Miroslaw Dynia, Miroslaw Korzeniowski |
| 2005 | Improving the Alphabet-Size in High Noise, Almost Optimal Rate List Decodable Codes. Eran Rom, Amnon Ta-Shma |
| 2005 | Increasing Kolmogorov Complexity. Harry Buhrman, Lance Fortnow, Ilan Newman, Nikolai K. Vereshchagin |
| 2005 | Information Theory in Property Testing and Monotonicity Testing in Higher Dimension. Nir Ailon, Bernard Chazelle |
| 2005 | Kolmogorov-Loveland Randomness and Stochasticity. Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann, Frank Stephan |
| 2005 | Minimizing NFA's and Regular Expressions. Gregor Gramlich, Georg Schnitger |
| 2005 | More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP. Lars Engebretsen, Jonas Holmerin |
| 2005 | On Nash Equilibria in Non-cooperative All-Optical Networks. Vittorio Bilò, Michele Flammini, Luca Moscardelli |
| 2005 | On Weighted Balls-into-Bins Games. Petra Berenbrink, Tom Friedetzky, Zengjian Hu, Russell A. Martin |
| 2005 | On the Computational Complexity of the Forcing Chromatic Number. Frank Harary, Wolfgang Slany, Oleg Verbitsky |
| 2005 | On the Decidability of Temporal Properties of Probabilistic Pushdown Automata. Tomás Brázdil, Antonín Kucera, Oldrich Strazovský |
| 2005 | Packet Buffering: Randomization Beats Deterministic Algorithms. Markus Schmidt |
| 2005 | Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size. Jianer Chen, Henning Fernau, Iyad A. Kanj, Ge Xia |
| 2005 | Pattern Occurrences in Multicomponent Models. Massimiliano Goldwurm, Violetta Lonati |
| 2005 | Polylog-Time Reductions Decrease Dot-Depth. Christian Glaßer |
| 2005 | Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms. Hubie Chen |
| 2005 | Quantum Interactive Proofs with Competing Provers. Gus Gutoski, John Watrous |
| 2005 | Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations. Kousha Etessami, Mihalis Yannakakis |
| 2005 | Regular Tree Languages Definable in FO. Michael Benedikt, Luc Segoufin |
| 2005 | Robust Polynomials and Quantum Algorithms. Harry Buhrman, Ilan Newman, Hein Röhrig, Ronald de Wolf |
| 2005 | Roundings Respecting Hard Constraints. Benjamin Doerr |
| 2005 | STACS 2005, 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005, Proceedings Volker Diekert, Bruno Durand |
| 2005 | Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms. Petros Drineas, Ravi Kannan, Michael W. Mahoney |
| 2005 | Shortest Monotone Descent Path Problem in Polyhedral Terrain. Sasanka Roy, Sandip Das, Subhas C. Nandy |
| 2005 | Solving Medium-Density Subset Sum Problems in Expected Polynomial Time. Abraham Flaxman, Bartosz Przydatek |
| 2005 | Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves. Gianni Franceschini |
| 2005 | Speed Scaling to Manage Temperature. Nikhil Bansal, Kirk Pruhs |
| 2005 | The Complexity of Solving Linear Equations over a Finite Ring. Vikraman Arvind, T. C. Vijayaraghavan |
| 2005 | The Core of a Countably Categorical Structure. Manuel Bodirsky |
| 2005 | The PIGs Full Monty - A Floor Show of Minimal Separators. Gerard Jennhwa Chang, Ton Kloks, Jiping Liu, Sheng-Lung Peng |
| 2005 | The Power of Commuting with Finite Sets of Words. Michal Kunc |
| 2005 | The Variable Hierarchy of the µ-Calculus Is Strict. Dietmar Berwanger, Giacomo Lenzi |
| 2005 | Three Optimal Algorithms for Balls of Three Colors. Zdenek Dvorák, Vít Jelínek, Daniel Král, Jan Kyncl, Michael E. Saks |
| 2005 | Topological Automata. Emmanuel Jeandel |
| 2005 | Truthful Approximation Mechanisms for Scheduling Selfish Related Machines. Nir Andelman, Yossi Azar, Motti Sorani |
| 2005 | Varieties of Codes and Kraft Inequality. Fabio Burderi, Antonio Restivo |
| 2005 | Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics. Carsten Witt |