| 2008 | SPREAD: an adaptive scheme for redundant and fair storage in dynamic heterogeneous storage systems. | Mario Mense, Christian Scheideler |
| 2008 | Strongly polynomial and fully combinatorial algorithms for bisubmodular function minimization. | S. Thomas McCormick, Satoru Fujishige |
| 2008 | Yet another algorithm for dense max cut: go greedy. | Claire Mathieu, Warren Schudy |
| 2008 | Distributed broadcast in unknown radio networks. | Gianluca De Marco |
| 2008 | Linked decompositions of networks and the power of choice in Polya urns. | Henry C. Lin, Christos Amanatidis, Martha Sideri, Richard M. Karp, Christos H. Papadimitriou |
| 2008 | Estimators and tail bounds for dimension reduction in | Ping Li |
| 2008 | Metric clustering via consistent labeling. | Robert Krauthgamer, Tim Roughgarden |
| 2008 | The UGC hardness threshold of the ℓ | Guy Kindler, Assaf Naor, Gideon Schechtman |
| 2008 | A nearly linear time algorithm for the half integral disjoint paths packing. | Ken-ichi Kawarabayashi, Bruce A. Reed |
| 2008 | Fast asynchronous byzantine agreement and leader election with full information. | Bruce M. Kapron, David Kempe, Valerie King, Jared Saia, Vishal Sanwalani |
| 2008 | Arc-disjoint in-trees in directed graphs. | Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa |
| 2008 | A deterministic sub-linear time sparse fourier algorithm via non-adaptive compressed sensing methods. | Mark A. Iwen |
| 2008 | Declaring independence via the sketching of sketches. | Piotr Indyk, Andrew McGregor |
| 2008 | Explicit constructions for compressed sensing of sparse signals. | Piotr Indyk |
| 2008 | Fast approximation of the permanent for very dense problems. | Mark Huber, Jenny Law |
| 2008 | Trace reconstruction with constant deletion probability and related results. | Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, Udi Wieder |
| 2008 | A fractional model of the border gateway protocol (BGP). | Penny E. Haxell, Gordon T. Wilfong |
| 2008 | L(2, 1)-labelling of graphs. | Frdric Havet, Bruce A. Reed, Jean-Sbastien Sereni |
| 2008 | Matroid intersection, pointer chasing, and Young's seminormal representation of | Nicholas J. A. Harvey |
| 2008 | Minimizing average latency in oblivious routing. | Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Rcke, Jaikumar Radhakrishnan |
| 2008 | Fully polynomial time approximation schemes for stochastic dynamic programs. | Nir Halman, Diego Klabjan, Chung-Lun Li, James B. Orlin, David Simchi-Levi |
| 2008 | Concatenated codes can achieve list-decoding capacity. | Venkatesan Guruswami, Atri Rudra |
| 2008 | Almost Euclidean subspaces of l | Venkatesan Guruswami, James R. Lee, Alexander A. Razborov |
| 2008 | Fast and reliable reconstruction of phylogenetic trees with very short edges. | Ilan Gronau, Shlomo Moran, Sagi Snir |
| 2008 | Improved algorithms for fully dynamic geometric spanners and geometric routing. | Lee-Ad Gottlieb, Liam Roditty |