| 2005 | An asymptotic approximation scheme for multigraph edge coloring. | Peter Sanders, David Steurer |
| 2005 | Selfish routing with atomic players. | Tim Roughgarden |
| 2005 | Strictly convex drawings of planar graphs. | Gnter Rote |
| 2005 | Distributed online call control on general networks. | Harald Rcke, Adi Rosn |
| 2005 | Towards a complete characterization of tries. | GaHyun Park, Wojciech Szpankowski |
| 2005 | The complexity of low-distortion embeddings between point sets. | Christos H. Papadimitriou, Shmuel Safra |
| 2005 | Computing equilibria in multi-player games. | Christos H. Papadimitriou, Tim Roughgarden |
| 2005 | Efficient hashing with lookups in two memory accesses. | Rina Panigrahy |
| 2005 | Can the TPRI structure help us to solve the algebraic eigenproblem? | Victor Y. Pan |
| 2005 | An optimal Bloom filter replacement. | Anna Pagh, Rasmus Pagh, S. Srinivasa Rao |
| 2005 | Optimal random number generation from a biased coin. | Sung-Il Pae, Michael C. Loui |
| 2005 | Approximating connectivity augmentation problems. | Zeev Nutov |
| 2005 | Analyzing and characterizing small-world graphs. | Van Nguyen, Charles U. Martel |
| 2005 | The bin-covering technique for thresholding random geometric graph properties. | S. Muthukrishnan, Gopal Pandurangan |
| 2005 | Testing hierarchical systems. | Damon Mosk-Aoyama, Mihalis Yannakakis |
| 2005 | Multicoloring unit disk graphs on triangular lattice points. | Yuichiro Miyamoto, Tomomi Matsui |
| 2005 | Lower bounds on the size of selection and rank indexes. | Peter Bro Miltersen |
| 2005 | A new look at survey propagation and its generalizations. | Elitza N. Maneva, Elchanan Mossel, Martin J. Wainwright |
| 2005 | Quantum algorithms for the triangle problem. | Frdric Magniez, Miklos Santha, Mario Szegedy |
| 2005 | An optimal online algorithm for packet scheduling with agreeable deadlines. | Fei Li, Jay Sethuraman, Clifford Stein |
| 2005 | A constant approximation algorithm for the one-warehouse multi-retailer problem. | Retsef Levi, Robin Roundy, David B. Shmoys |
| 2005 | Network coding: does the model need tuning? | April Rasala Lehman, Eric P. Lehman |
| 2005 | Distributions of points in the unit-square and large | Hanno Lefmann |
| 2005 | On distance scales, embeddings, and efficient relaxations of the cut cone. | James R. Lee |
| 2005 | Online ascending auctions for gradually expiring items. | Ron Lavi, Noam Nisan |