| 2005 | A BDD-Representation for the Logic of Equality and Uninterpreted Functions. Jaco van de Pol, Olga Tveretina |
| 2005 | A Bridge Between the Asynchronous Message Passing Model and Local Computations in Graphs. Jérémie Chalopin, Yves Métivier |
| 2005 | Abstract Numeration Systems and Tilings. Valérie Berthé, Michel Rigo |
| 2005 | Adversarial Queueing Model for Continuous Network Dynamics. Maria J. Blesa, Daniel Calzada, Antonio Fernández, Luis López, Andrés L. Martínez, Agustín Santos, Maria J. Serna |
| 2005 | Algebras as Knowledge Structures. Bernhard Heinemann |
| 2005 | An Asymptotically Optimal Linear-Time Algorithm for Locally Consistent Constraint Satisfaction Problems. Daniel Král, Ondrej Pangrác |
| 2005 | An Efficient Algorithm for Computing Optimal Discrete Voltage Schedules. Minming Li, Frances F. Yao |
| 2005 | An Exact 2.9416 Tobias Riege, Jörg Rothe |
| 2005 | An Invitation to Play. Wieslaw Zielonka |
| 2005 | Approximating Polygonal Objects by Deformable Smooth Surfaces. Ho-Lun Cheng, Tony Tan |
| 2005 | Approximating Reversal Distance for Strings with Bounded Number of Duplicates. Petr Kolman |
| 2005 | Asynchronous Deterministic Rendezvous in Graphs. Gianluca De Marco, Luisa Gargano, Evangelos Kranakis, Danny Krizanc, Andrzej Pelc, Ugo Vaccaro |
| 2005 | Autoreducibility, Mitoticity, and Immunity. Christian Glaßer, Mitsunori Ogihara, Aduri Pavan, Alan L. Selman, Liyu Zhang |
| 2005 | Basic Mereology with Equivalence Relations. Ryszard Janicki |
| 2005 | Basic Properties for Sand Automata. Julien Cervelle, Enrico Formenti, Benoît Masson |
| 2005 | Basis of Solutions for a System of Linear Inequalities in Integers: Computation and Applications. Dimitri Chubarov, Andrei Voronkov |
| 2005 | Canonical Disjoint NP-Pairs of Propositional Proof Systems. Christian Glaßer, Alan L. Selman, Liyu Zhang |
| 2005 | Coloring Sparse Random Julia Böttcher |
| 2005 | Combining Self-reducibility and Partial Information Algorithms. André Hernich, Arfst Nickelsen |
| 2005 | Completeness and Degeneracy in Information Dynamics of Cellular Automata. Hidenosuke Nishio |
| 2005 | Complexity Bounds for Regular Games. Paul Hunter, Anuj Dawar |
| 2005 | Complexity of DNF and Isomorphism of Monotone Formulas. Judy Goldsmith, Matthias Hagen, Martin Mundhenk |
| 2005 | Concurrent Automata vs. Asynchronous Systems. Rémi Morin |
| 2005 | D-Width: A More Natural Measure for Directed Tree Width. Mohammad Ali Safari |
| 2005 | Dimension Is Compression. María López-Valdés, Elvira Mayordomo |
| 2005 | Event Structures for the Collective Tokens Philosophy of Inhibitor Nets. G. Michele Pinna |
| 2005 | Explicit Inapproximability Bounds for the Shortest Superstring Problem. Virginia Vassilevska |
| 2005 | Finding Exact and Maximum Occurrences of Protein Complexes in Protein-Protein Interaction Graphs. Guillaume Fertin, Romeo Rizzi, Stéphane Vialette |
| 2005 | Fully Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata. Nazim Fatès, Michel Morvan, Nicolas Schabanel, Eric Thierry |
| 2005 | Generating All Minimal Integral Solutions to Monotone and, or-Systems of Linear, Transversal and Polymatroid Inequalities. Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich |
| 2005 | Goals in the Propositional Horn Language Are Monotone Boolean Circuits. Joxe Gaintzarain, Montserrat Hermo, Marisa Navarro |
| 2005 | Greedy Approximation via Duality for Packing, Combinatorial Auctions and Routing. Piotr Krysta |
| 2005 | Interactive Algorithms 2005. Yuri Gurevich |
| 2005 | Inverse Monoids: Decidability and Complexity of Algebraic Questions. Markus Lohrey, Nicole Ondrusch |
| 2005 | Isomorphic Implication. Michael Bauland, Edith Hemaspaandra |
| 2005 | Knot Theory, Jones Polynomial and Quantum Computing. Rusins Freivalds |
| 2005 | Languages Representable by Vertex-Labeled Graphs. Igor Grunsky, Oleksiy Kurganskyy, Igor Potapov |
| 2005 | Linearly Bounded Infinite Graphs. Arnaud Carayol, Antoine Meyer |
| 2005 | Mathematical Foundations of Computer Science 2005, 30th International Symposium, MFCS 2005, Gdansk, Poland, August 29 - September 2, 2005, Proceedings Joanna Jedrzejowicz, Andrzej Szepietowski |
| 2005 | Matrix and Graph Orders Derived from Locally Constrained Graph Homomorphisms. Jirí Fiala, Daniël Paulusma, Jan Arne Telle |
| 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 | Nondeterministic Graph Searching: From Pathwidth to Treewidth. Fedor V. Fomin, Pierre Fraigniaud, Nicolas Nisse |
| 2005 | On Beta-Shifts Having Arithmetical Languages. Jakob Grue Simonsen |
| 2005 | On Small Hard Leaf Languages. Falk Unger |
| 2005 | On the Communication Complexity of Co-linearity Problems. Andrew Chi-Chih Yao |
| 2005 | On the Complexity of Depth-2 Circuits with Threshold Gates. Kazuyuki Amano, Akira Maruoka |
| 2005 | On the Complexity of Mixed Discriminants and Related Problems. Leonid Gurvits |
| 2005 | On the Number of Random Digits Required in MonteCarlo Integration of Definable Functions. César Luis Alonso, José Luis Montaña, Luis Miguel Pardo |
| 2005 | On the Parameterized Complexity of Exact Satisfiability Problems. Joachim Kneis, Daniel Mölle, Stefan Richter, Peter Rossmanith |
| 2005 | Online Interval Coloring with Packing Constraints. Leah Epstein, Meital Levy |
| 2005 | Online and Dynamic Recognition of Squarefree Strings. Jesper Jansson, Zeshan Peng |
| 2005 | Packing Weighted Rectangles into a Square. Aleksei V. Fishkin, Olga Gerber, Klaus Jansen, Roberto Solis-Oba |
| 2005 | Page Migration in Dynamic Networks. Marcin Bienkowski, Friedhelm Meyer auf der Heide |
| 2005 | Pure Nash Equilibria in Games with a Large Number of Actions. Carme Àlvarez, Joaquim Gabarró, Maria J. Serna |
| 2005 | Random Databases and Threshold for Monotone Non-recursive Datalog. Konstantin Korovin, Andrei Voronkov |
| 2005 | Reconstructing an Ultrametric Galled Phylogenetic Network from a Distance Matrix. Ho-Leung Chan, Jesper Jansson, Tak Wah Lam, Siu-Ming Yiu |
| 2005 | Regular Sets of Higher-Order Pushdown Stacks. Arnaud Carayol |
| 2005 | Removing Bidirectionality from Nondeterministic Finite Automata. Christos A. Kapoutsis |
| 2005 | Separating the Notions of Self- and Autoreducibility. Piotr Faliszewski, Mitsunori Ogihara |
| 2005 | Shrinking Restarting Automata. Tomasz Jurdzinski, Friedrich Otto |
| 2005 | Some Computational Issues in Membrane Computing. Oscar H. Ibarra |
| 2005 | Stratified Boolean Grammars. Michal Wrona |
| 2005 | Strict Language Inequalities and Their Decision Problems. Alexander Okhotin |
| 2005 | The Complexity of Model Checking Higher Order Fixpoint Logic. Martin Lange, Rafal Somla |
| 2005 | The Complexity of Satisfiability Problems: Refining Schaefer's Theorem. Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer |
| 2005 | The Expressive Power of Two-Variable Least Fixed-Point Logics. Martin Grohe, Stephan Kreutzer, Nicole Schweikardt |
| 2005 | The Generalization of Dirac's Theorem for Hypergraphs. Endre Szemerédi, Andrzej Rucinski, Vojtech Rödl |
| 2005 | Tight Approximability Results for the Maximum Solution Equation Problem over Z Fredrik Kuivinen |
| 2005 | Two Logical Hierarchies of Optimization Problems over the Real Numbers. Uffe Flarup Hansen, Klaus Meer |
| 2005 | Zeta-Dimension. David Doty, Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo, Philippe Moser |