| 2008 | Lagrangian Relaxation and Partial Cover (Extended Abstract). | Julin Mestre |
| 2008 | An Improved Randomized Truthful Mechanism for Scheduling Unrelated Machines. | Pinyan Lu, Changyuan Yu |
| 2008 | Lower bounds for adaptive linearity tests. | Shachar Lovett |
| 2008 | Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental. | Zvi Lotker, Boaz Patt-Shamir, Dror Rawitz |
| 2008 | A Theory for Valiant's Matchcircuits (Extended Abstract). | Angsheng Li, Mingji Xia |
| 2008 | Geometric Set Cover and Hitting Sets for Polytopes in R | Sren Laue |
| 2008 | Compatibility of Shelah and Stupp's and Muchnik's iteration with fragments of monadic second order logic. | Dietrich Kuske |
| 2008 | New Combinatorial Complete One-Way Functions. | Arist Kojevnikov, Sergey I. Nikolenko |
| 2008 | Ehrenfeucht-Frass Goes Automatic for Real Addition. | Felix Klaedtke |
| 2008 | Space Hierarchy Results for Randomized Models. | Jeff Kinne, Dieter van Melkebeek |
| 2008 | The Frobenius Problem in a Free Monoid. | Jui-Yi Kao, Jeffrey O. Shallit, Zhi Xu |
| 2008 | On the Induced Matching Problem. | Iyad A. Kanj, Michael J. Pelsmajer, Ge Xia, Marcus Schaefer |
| 2008 | Cardinality and counting quantifiers on omega-automatic structures. | Lukasz Kaiser, Sasha Rubin, Vince Brny |
| 2008 | Improved Algorithms for the Range Next Value Problem and Applications. | Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Mohammad Sohel Rahman, Tomasz Walen |
| 2008 | Computing Minimum Spanning Trees with Uncertainty. | Michael Hoffmann, Thomas Erlebach, Danny Krizanc, Mats Mihalk, Rajeev Raman |
| 2008 | Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees. | Viet Tung Hoang, Wing-Kin Sung |
| 2008 | On the Complexity of Elementary Modal Logics. | Edith Hemaspaandra, Henning Schnoor |
| 2008 | Efficient Algorithms for Membership in Boolean Hierarchies of Regular Languages. | Christian Glaer, Heinz Schmitz, Victor L. Selivanov |
| 2008 | Succinctness of the Complement and Intersection of Regular Expressions. | Wouter Gelade, Frank Neven |
| 2008 | Order-Invariant MSO is Stronger than Counting MSO in the Finite. | Tobias Ganzow, Sasha Rubin |
| 2008 | Model Checking Games for the Quantitative -Calculus. | Diana Fischer, Erich Grdel, Lukasz Kaiser |
| 2008 | Convergence Thresholds of Newton's Method for Monotone Polynomial Equations. | Javier Esparza, Stefan Kiefer, Michael Luttenberger |
| 2008 | Trimming of Graphs, with Application to Point Labeling. | Thomas Erlebach, Torben Hagerup, Klaus Jansen, Moritz Minzlaff, Alexander Wolff |
| 2008 | Discrete Jordan Curve Theorem: A proof formalized in Coq with hypermaps. | Jean-Franois Dufourd |
| 2008 | Tight Bounds for Blind Search on the Integers. | Martin Dietzfelbinger, Jonathan E. Rowe, Ingo Wegener, Philipp Woelfel |