| 2008 | The Local Nature of List Colorings for Graphs of High Girth. | Flavio Chierichetti, Andrea Vattani |
| 2008 | Understanding the Complexity of Induced Subgraph Isomorphisms. | Yijia Chen, Marc Thurley, Mark Weyer |
| 2008 | Complexity of Decoding Positive-Rate Reed-Solomon Codes. | Qi Cheng, Daqing Wan |
| 2008 | Quantified Constraint Satisfaction and the Polynomially Generated Powers Property. | Hubie Chen |
| 2008 | Algorithms for 2-Route Cut Problems. | Chandra Chekuri, Sanjeev Khanna |
| 2008 | Finding a Maximum Matching in a Sparse Random Graph in O(n) Expected Time. | Prasad Chebolu, Alan M. Frieze, Pll Melsted |
| 2008 | Networks Become Navigable as Nodes Move and Forget. | Augustin Chaintreau, Pierre Fraigniaud, Emmanuelle Lebhar |
| 2008 | How to Protect Yourself without Perfect Shredding. | Ran Canetti, Dror Eiger, Shafi Goldwasser, Dah-Yoh Lim |
| 2008 | Extractable Perfectly One-Way Functions. | Ran Canetti, Ronny Ramzi Dakdouk |
| 2008 | Composable Formal Security Analysis: Juggling Soundness, Simplicity and Efficiency. | Ran Canetti |
| 2008 | The Complexity of the Counting Constraint Satisfaction Problem. | Andrei A. Bulatov |
| 2008 | The Complexity of Boolean Formula Minimization. | David Buchfuhrer, Christopher Umans |
| 2008 | Uniform Budgets and the Envy-Free Pricing Problem. | Patrick Briest |
| 2008 | Controller Synthesis and Verification for Markov Decision Processes with Qualitative Branching Time Objectives. | Toms Brzdil, Vojtech Forejt, Antonn Kucera |
| 2008 | On Expressiveness and Complexity in Real-Time Model Checking. | Patricia Bouyer, Nicolas Markey, Jol Ouaknine, James Worrell |
| 2008 | The Two-Edge Connectivity Survivable Network Problem in Planar Graphs. | Glencora Borradaile, Philip N. Klein |
| 2008 | On Berge Multiplication for Monotone Boolean Dualization. | Endre Boros, Khaled M. Elbassioni, Kazuhisa Makino |
| 2008 | Tree Languages Defined in First-Order Logic with One Quantifier Alternation. | Mikolaj Bojanczyk, Luc Segoufin |
| 2008 | On the Sets of Real Numbers Recognized by Finite Automata in Multiple Bases. | Bernard Boigelot, Julien Brusten, Vronique Bruyre |
| 2008 | On Problems without Polynomial Kernels (Extended Abstract). | Hans L. Bodlaender, Rodney G. Downey, Michael R. Fellows, Danny Hermelin |
| 2008 | Non-dichotomies in Constraint Satisfaction Complexity. | Manuel Bodirsky, Martin Grohe |
| 2008 | A New Combinatorial Approach for Sparse Graph Problems. | Guy E. Blelloch, Virginia Vassilevska, Ryan Williams |
| 2008 | Asymptotically Optimal Hitting Sets Against Polynomials. | Markus Blser, Moritz Hardt, David Steurer |
| 2008 | The Tractability Frontier for NFA Minimization. | Henrik Bjrklund, Wim Martens |
| 2008 | The Travelling Salesman Problem in Bounded Degree Graphs. | Andreas Bjrklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto |