| 2008 | Lower Bounds for Syntactically Multilinear Algebraic Branching Programs. | Maurice J. Jansen |
| 2008 | Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations. | Christian Hundt, Maciej Liskiewicz |
| 2008 | A Note on k-Colorability of P5-Free Graphs. | Chnh T. Hong, Marcin Kaminski, Vadim V. Lozin, Joe Sawada, Xiao Shu |
| 2008 | Nilpotency and Limit Sets of Cellular Automata. | Pierre Guillon, Gatan Richard |
| 2008 | A Robust Class of Regular Languages. | Antonio Cano Gmez, Jean-Eric Pin |
| 2008 | On Synchronous and Asynchronous Interaction in Distributed Systems. | Rob J. van Glabbeek, Ursula Goltz, Jens-Wolfhard Schicke |
| 2008 | Succinctness of Regular Expressions with Interleaving, Intersection and Counting. | Wouter Gelade |
| 2008 | Complexity and Limiting Ratio of Boolean Functions over Implication. | Herv Fournier, Danile Gardy, Antoine Genitrini, Bernhard Gittenberger |
| 2008 | Iterative Compression and Exact Algorithms. | Fedor V. Fomin, Serge Gaspers, Dieter Kratsch, Mathieu Liedloff, Saket Saurabh |
| 2008 | Reversal-Bounded Counter Machines Revisited. | Alain Finkel, Arnaud Sangnier |
| 2008 | Sincere-Strategy Preference-Based Approval Voting Broadly Resists Control. | Gbor Erdlyi, Markus Nowak, Jrg Rothe |
| 2008 | Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems. | Michael Elberfeld, Till Tantau |
| 2008 | A PTAS for the Sparsest Spanners Problem on Apex-Minor-Free Graphs. | Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach |
| 2008 | Complexity of Data Tree Patterns over XML Documents. | Claire David |
| 2008 | On a Special Class of Primitive Words. | Elena Czeizler, Lila Kari, Shinnosuke Seki |
| 2008 | Regional Languages and Tiling: A Unifying Approach to Picture Grammars. | Alessandra Cherubini, Stefano Crespi-Reghizzi, Matteo Pradella |
| 2008 | A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems. | Emilie Charlier, Michel Rigo |
| 2008 | Arthur and Merlin as Oracles. | Venkatesan T. Chakaravarthy, Sambuddha Roy |
| 2008 | Positional Strategies for Higher-Order Pushdown Parity Games. | Arnaud Carayol, Michaela Slaats |
| 2008 | A 6/5-Approximation Algorithm for the Maximum 3-Cover Problem. | Ioannis Caragiannis, Gianpiero Monaco |
| 2008 | Computing Sharp 2-Factors in Claw-Free Graphs. | Hajo Broersma, Danil Paulusma |
| 2008 | Flip Algorithm for Segment Triangulations. | Mathieu Brvilliers, Nicolas Chevallier, Dominique Schmitt |
| 2008 | On the Shortest Linear Straight-Line Program for Computing Linear Forms. | Joan Boyar, Philip Matthews, Ren Peralta |
| 2008 | Clustering with Partial Information. | Hans L. Bodlaender, Michael R. Fellows, Pinar Heggernes, Federico Mancini, Charis Papadopoulos, Frances A. Rosamond |
| 2008 | Reoptimization of the Metric Deadline TSP. | Hans-Joachim Bckenhauer, Dennis Komm |