| 2008 | Duality and Equational Theory of Regular Languages. | Mai Gehrke, Serge Grigorieff, Jean-Eric Pin |
| 2008 | Dynamic Normal Forms and Dynamic Characteristic Polynomial. | Gudmund Skovbjerg Frandsen, Piotr Sankowski |
| 2008 | Treewidth Computation and Extremal Combinatorics. | Fedor V. Fomin, Yngve Villanger |
| 2008 | Robust Multi-property Combiners for Hash Functions Revisited. | Marc Fischlin, Anja Lehmann, Krzysztof Pietrzak |
| 2008 | Computational Complexity of the Distance Constrained Labeling Problem for Trees (Extended Abstract). | Jir Fiala, Petr A. Golovach, Jan Kratochvl |
| 2008 | The Speed of Convergence in Congestion Games under Best-Response Dynamics. | Angelo Fanelli, Michele Flammini, Luca Moscardelli |
| 2008 | Recursive Stochastic Games with Positive Rewards. | Kousha Etessami, Dominik Wojtczak, Mihalis Yannakakis |
| 2008 | Newton's Method for omega-Continuous Semirings. | Javier Esparza, Stefan Kiefer, Michael Luttenberger |
| 2008 | Approximative Methods for Monotone Systems of Min-Max-Polynomial Equations. | Javier Esparza, Thomas Gawlitza, Stefan Kiefer, Helmut Seidl |
| 2008 | Quantum SAT for a Qutrit-Cinquit Pair Is QMA1-Complete. | Lior Eldar, Oded Regev |
| 2008 | A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation. | Friedrich Eisenbrand, Thomas Rothvo |
| 2008 | Directed st-Connectivity Is Not Expressible in Symmetric Datalog. | Lszl Egri, Benot Larose, Pascal Tesson |
| 2008 | Spanners in Sparse Graphs. | Feodor F. Dragan, Fedor V. Fomin, Petr A. Golovach |
| 2008 | Could SFLASH be Repaired?. | Jintai Ding, Vivien Dubois, Bo-Yin Yang, Chia-Hsin Owen Chen, Chen-Mou Cheng |
| 2008 | Competitive Weighted Matching in Transversal Matroids. | Nedialko B. Dimitrov, C. Greg Plaxton |
| 2008 | Succinct Data Structures for Retrieval and Approximate Membership (Extended Abstract). | Martin Dietzfelbinger, Rasmus Pagh |
| 2008 | Efficiently Testing Sparse GF(2) Polynomials. | Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Rocco A. Servedio, Andrew Wan |
| 2008 | On Datalog vs. LFP. | Anuj Dawar, Stephan Kreutzer |
| 2008 | Optimal Cryptographic Hardness of Learning Monotone Functions. | Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee |
| 2008 | Graph Structure and Monadic Second-Order Logic: Language Theoretical Aspects. | Bruno Courcelle |
| 2008 | The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata. | Thomas Colcombet, Christof Lding |
| 2008 | Interacting Quantum Observables. | Bob Coecke, Ross Duncan |
| 2008 | Function Evaluation Via Linear Programming in the Priced Information Model. | Ferdinando Cicalese, Eduardo Sany Laber |
| 2008 | Bayesian Combinatorial Auctions. | George Christodoulou, Annamria Kovcs, Michael Schapira |
| 2008 | Optimal Quantum Adversary Lower Bounds for Ordered Search. | Andrew M. Childs, Troy Lee |