| 2005 | Maximum-likelihood decoding of Reed-Solomon codes is NP-hard. | Venkatesan Guruswami, Alexander Vardy |
| 2005 | On profit-maximizing envy-free pricing. | Venkatesan Guruswami, Jason D. Hartline, Anna R. Karlin, David Kempe, Claire Kenyon, Frank McSherry |
| 2005 | Optimizing markov models with applications to triangular connectivity coding. | Stefan Gumhold |
| 2005 | Rounds vs queries trade-off in noisy computation. | Navin Goyal, Michael E. Saks |
| 2005 | Collusion-resistant mechanisms for single-parameter agents. | Andrew V. Goldberg, Jason D. Hartline |
| 2005 | Computing the shortest path: | Andrew V. Goldberg, Chris Harrelson |
| 2005 | Random planar graphs with | Stefanie Gerke, Colin McDiarmid, Angelika Steger, Andreas Weil |
| 2005 | Dominator tree verification and vertex-disjoint paths. | Loukas Georgiadis, Robert Endre Tarjan |
| 2005 | Improved approximation for universal facility location. | Naveen Garg, Rohit Khandekar, Vinayaka Pandit |
| 2005 | The expected value of random minimal length spanning tree of a complete graph. | David Gamarnik |
| 2005 | Approximating the smallest | Harold N. Gabow, Michel X. Goemans, va Tardos, David P. Williamson |
| 2005 | Dissections and trees, with applications to optimal mesh encoding and to random sampling. | ric Fusy, Dominique Poulalhon, Gilles Schaeffer |
| 2005 | Controlled perturbation for Delaunay triangulations. | Stefan Funke, Christian Klein, Kurt Mehlhorn, Susanne Schmitt |
| 2005 | Online convex optimization in the bandit setting: gradient descent without a gradient. | Abraham Flaxman, Adam Tauman Kalai, H. Brendan McMahan |
| 2005 | Adversarial deletion in a scale free random graph process. | Abraham Flaxman, Alan M. Frieze, Juan Vera |
| 2005 | On the random 2-stage minimum spanning tree. | Abraham D. Flaxman, Alan M. Frieze, Michael Krivelevich |
| 2005 | Online conflict-free coloring for intervals. | Amos Fiat, Meital Levy, Jir Matousek, Elchanan Mossel, Jnos Pach, Micha Sharir, Shakhar Smorodinsky, Uli Wagner, Emo Welzl |
| 2005 | LP decoding achieves capacity. | Jon Feldman, Clifford Stein |
| 2005 | Graph distances in the streaming model: the value of space. | Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang |
| 2005 | Rigorous analysis of heuristics for NP-hard problems. | Uriel Feige |
| 2005 | Finding large cycles in Hamiltonian graphs. | Toms Feder, Rajeev Motwani |
| 2005 | Two algorithms for general list matrix partitions. | Toms Feder, Pavol Hell, Daniel Krl, Jir Sgall |
| 2005 | Fast convergence of selfish rerouting. | Eyal Even-Dar, Yishay Mansour |
| 2005 | Greedy optimal homotopy and homology generators. | Jeff Erickson, Kim Whittlesey |
| 2005 | Lower bounds for external algebraic decision trees. | Jeff Erickson |