| 2008 | Collective Additive Tree Spanners of Homogeneously Orderable Graphs. | Feodor F. Dragan, Chenyu Yan, Yang Xiang |
| 2008 | Energy Efficient Monitoring in Sensor Networks. | Amol Deshpande, Samir Khuller, Azarakhsh Malekian, Mohammed Toossi |
| 2008 | Simpler Constant-Seed Condensers. | Domingos Dellamonica Jr. |
| 2008 | Approximation Algorithms for k-Hurdle Problems. | Brian C. Dean, Adam Griffis, Adam Whitley |
| 2008 | Random 2-XORSAT at the Satisfiability Threshold. | Herv Daud, Vlady Ravelomanana |
| 2008 | Local Algorithms for Dominating and Connected Dominating Sets of Unit Disk Graphs with Location Aware Nodes. | Jurek Czyzowicz, Stefan Dobrev, Thomas Fevens, Hernn Gonzlez-Aguilar, Evangelos Kranakis, Jaroslav Opatrny, Jorge Urrutia |
| 2008 | On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints. | Grard Cornujols, Franois Margot |
| 2008 | The Online Transportation Problem: On the Exponential Boost of One Extra Server. | Christine Chung, Kirk Pruhs, Patchrawat Uthaisombut |
| 2008 | The Generalized Median Stable Matchings: Finding Them Is Not That Easy. | Christine T. Cheng |
| 2008 | A Representation Theorem for Union-Difference Families and Application. | Binh-Minh Bui-Xuan, Michel Habib |
| 2008 | Ptolemaic Graphs and Interval Graphs Are Leaf Powers. | Andreas Brandstdt, Christian Hundt |
| 2008 | Spanners of Complete k -Partite Geometric Graphs. | Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Pat Morin, Michiel H. M. Smid |
| 2008 | Spanning Trees with Many Leaves in Graphs without Diamonds and Blossoms. | Paul S. Bonsma, Florian Zickfeld |
| 2008 | Geometric Aspects of Online Packet Buffering: An Optimal Randomized Algorithm for Two Buffers. | Marcin Bienkowski, Aleksander Madry |
| 2008 | Origami Embedding of Piecewise-Linear Two-Manifolds. | Marshall W. Bern, Barry Hayes |
| 2008 | Simplifying 3D Polygonal Chains Under the Discrete Frchet Distance. | Sergey Bereg, Minghui Jiang, Wencheng Wang, Boting Yang, Binhai Zhu |
| 2008 | Paths with no Small Angles. | Imre Brny, Attila Pr, Pavel Valtr |
| 2008 | Comparing and Aggregating Partially Resolved Trees. | Mukul S. Bansal, Jianrong Dong, David Fernndez-Baca |
| 2008 | Average Rate Speed Scaling. | Nikhil Bansal, David P. Bunde, Ho-Leung Chan, Kirk Pruhs |
| 2008 | Parallel Repetition of the Odd Cycle Game. | Kooshiar Azimian, Mario Szegedy |
| 2008 | Stateless Near Optimal Flow Control with Poly-logarithmic Convergence. | Baruch Awerbuch, Rohit Khandekar |
| 2008 | Sorting and Selection with Random Costs. | Stanislav Angelov, Keshav Kunal, Andrew McGregor |
| 2008 | List Update with Locality of Reference. | Spyros Angelopoulos, Reza Dorrigiv, Alejandro Lpez-Ortiz |
| 2008 | Coloring Geometric Range Spaces. | Greg Aloupis, Jean Cardinal, Sbastien Collette, Stefan Langerman, Shakhar Smorodinsky |
| 2008 | Speeding-Up Lattice Reduction with Random Projections (Extended Abstract). | Ali Akhavi, Damien Stehl |