| 2008 | A Characterisation of the Relations Definable in Presburger Arithmetic. Mathias Barra |
| 2008 | A Characterization of NCk. Jean-Yves Marion, Romain Péchoux |
| 2008 | A Denotational Semantics for Total Correctness of Sequential Exact Real Programs. Thomas Anberrée |
| 2008 | A Linear-Time Algorithm for Finding All Door Locations That Make a Room Searchable. John Z. Zhang, Tsunehiko Kameda |
| 2008 | A Logic for Distributed Higher Order pi-Calculus. Zining Cao |
| 2008 | A Moderately Exponential Time Algorithm for Full Degree Spanning Tree. Serge Gaspers, Saket Saurabh, Alexey A. Stepanov |
| 2008 | A Practical Parameterized Algorithm for the Individual Haplotyping Problem MLF. Minzhu Xie, Jianxin Wang, Jianer Chen |
| 2008 | A Separation between Divergence and Holevo Information for Ensembles. Rahul Jain, Ashwin Nayak, Yi Su |
| 2008 | A Topological Study of Tilings. Grégory Lafitte, Michael Weiss |
| 2008 | A Well-Mixed Function with Circuit Complexity 5n±o(n): Tightness of the Lachish-Raz-Type Bounds. Kazuyuki Amano, Jun Tarui |
| 2008 | An Improved Parameterized Algorithm for a Generalized Matching Problem. Jianxin Wang, Dan Ning, Qilong Feng, Jianer Chen |
| 2008 | An O*(3.523k) Parameterized Algorithm for 3-Set Packing. Jianxin Wang, Qilong Feng |
| 2008 | Approximating Border Length for DNA Microarray Synthesis. Cindy Y. Li, Prudence W. H. Wong, Qin Xin, Fencol C. C. Yung |
| 2008 | Balancing Traffic Load Using One-Turn Rectilinear Routing. Stephane Durocher, Evangelos Kranakis, Danny Krizanc, Lata Narayanan |
| 2008 | Definable Filters in the Structure of Bounded Turing Reductions. Angsheng Li, Weilin Li, Yicheng Pan, Linqing Tang |
| 2008 | Derandomizing Graph Tests for Homomorphism. Angsheng Li, Linqing Tang |
| 2008 | Deterministic Hot-Potato Permutation Routing on the Mesh and the Torus. Andre Osterloh |
| 2008 | Differential Privacy: A Survey of Results. Cynthia Dwork |
| 2008 | Distance Constrained Labelings of Trees. Jirí Fiala, Petr A. Golovach, Jan Kratochvíl |
| 2008 | Efficient Algorithms for Model-Based Motif Discovery from Multiple Sequences. Bin Fu, Ming-Yang Kao, Lusheng Wang |
| 2008 | Extensions of Embeddings in the Computably Enumerable Degrees. Jitai Zhao |
| 2008 | Finding Minimum 3-Way Cuts in Hypergraphs. Mingyu Xiao |
| 2008 | Generalized Domination in Degenerate Graphs: A Complete Dichotomy of Computational Complexity. Petr A. Golovach, Jan Kratochvíl |
| 2008 | Generation Complexity Versus Distinction Complexity. Rupert Hölzl, Wolfgang Merkle |
| 2008 | Genome Rearrangement Algorithms for Unsigned Permutations with O(logn) Singletons. Xiaowen Lou, Daming Zhu |
| 2008 | Graphs of Linear Clique-Width at Most 3. Pinar Heggernes, Daniel Meister, Charis Papadopoulos |
| 2008 | Hamiltonicity of Matching Composition Networks with Conditional Edge Faults. Sun-Yuan Hsieh, Chia-Wei Lee |
| 2008 | Improved Algorithms for Bicluster Editing. Jiong Guo, Falk Hüffner, Christian Komusiewicz, Yong Zhang |
| 2008 | Inapproximability of Maximum Weighted Edge Biclique and Its Applications. Jinsong Tan |
| 2008 | Indistinguishability and First-Order Logic. Skip Jordan, Thomas Zeugmann |
| 2008 | Local 7-Coloring for Planar Subgraphs of Unit Disk Graphs. Jurek Czyzowicz, Stefan Dobrev, Hernán González-Aguilar, Rastislav Kralovic, Evangelos Kranakis, Jaroslav Opatrny, Ladislav Stacho, Jorge Urrutia |
| 2008 | Logical Closure Properties of Propositional Proof Systems. Olaf Beyersdorff |
| 2008 | Minimum Maximal Matching Is NP-Hard in Regular Bipartite Graphs. Marc Demange, Tínaz Ekim |
| 2008 | Model Theoretic Complexity of Automatic Structures (Extended Abstract). Bakhadyr Khoussainov, Mia Minnes |
| 2008 | More on Weak Bisimilarity of Normed Basic Parallel Processes. Haiyan Chen |
| 2008 | On a Question of Frank Stephan. Klaus Ambos-Spies, Serikzhan A. Badaev, Sergey Goncharov |
| 2008 | On the Complexity of Measurement in Classical Physics. Edwin J. Beggs, José Félix Costa, Bruno Loff, John V. Tucker |
| 2008 | On the Complexity of the Hidden Subgroup Problem. Stephen A. Fenner, Yong Zhang |
| 2008 | On the OBDD Complexity of the Most Significant Bit of Integer Multiplication. Beate Bollig |
| 2008 | Propositional Projection Temporal Logic, Bchi Automata and omega-Regular Expressions. Cong Tian, Zhenhua Duan |
| 2008 | Quantum Walk Based Search Algorithms. Miklos Santha |
| 2008 | Ratio Based Stable In-Place Merging. Pok-Son Kim, Arne Kutzner |
| 2008 | Search Space Reductions for Nearest-Neighbor Queries. Micah Adler, Brent Heeringa |
| 2008 | Speeding up Dynamic Programming for Some NP-Hard Graph Recoloring Problems. Oriana Ponta, Falk Hüffner, Rolf Niedermeier |
| 2008 | Symbolic Algorithm Analysis of Rectangular Hybrid Systems. Haibin Zhang, Zhenhua Duan |
| 2008 | The Non-isolating Degrees Are Upwards Dense in the Computably Enumerable Degrees. S. Barry Cooper, Matthew C. Salts, Guohua Wu |
| 2008 | The Structure of Detour Degrees. Lars Kristiansen, Paul J. Voda |
| 2008 | Theory and Applications of Models of Computation, 5th International Conference, TAMC 2008, Xi'an, China, April 25-29, 2008. Proceedings Manindra Agrawal, Ding-Zhu Du, Zhenhua Duan, Angsheng Li |
| 2008 | Total Degrees and Nonsplitting Properties of Enumeration Degrees. Marat M. Arslanov, S. Barry Cooper, Iskander Sh. Kalimullin, Mariya Ivanova Soskova |
| 2008 | Unary Automatic Graphs: An Algorithmic Perspective. Bakhadyr Khoussainov, Jiamou Liu, Mia Minnes |
| 2008 | Weak Bisimulations for the Giry Monad (Extended Abstract). Ernst-Erich Doberkat |
| 2008 | s-Degrees within e-Degrees. Thomas F. Kent |