| 2005 | Conformance testing in the presence of multiple faults. | Viraj Kumar, Mahesh Viswanathan |
| 2005 | Approximation algorithms for cycle packing problems. | Michael Krivelevich, Zeev Nutov, Raphael Yuster |
| 2005 | Complete partitions of graphs. | Guy Kortsarz, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian |
| 2005 | A group-strategyproof mechanism for Steiner forests. | Jochen Knemann, Stefano Leonardi, Guido Schfer |
| 2005 | Pianos are not flat: rigid motion planning in three dimensions. | Vladlen Koltun |
| 2005 | Provably good moving least squares. | Ravi Krishna Kolluri |
| 2005 | Girth restrictions for the 5-flow conjecture. | Martin Kochol |
| 2005 | Isomorphism and embedding problems for infinite limits of scale-free graphs. | Robert D. Kleinberg, Jon M. Kleinberg |
| 2005 | A multiple-choice secretary algorithm with applications to online auctions. | Robert D. Kleinberg |
| 2005 | Multiple-source shortest paths in planar graphs. | Philip N. Klein |
| 2005 | The hidden subgroup problem and permutation group theory. | Julia Kempe, Aner Shalev |
| 2005 | Online topological ordering. | Irit Katriel, Hans L. Bodlaender |
| 2005 | Algorithms for combining rooted triplets into a galled phylogenetic network. | Jesper Jansson, Nguyen Bao Nguyen, Wing-Kin Sung |
| 2005 | Market equilibria for homothetic, quasi-concave utilities and economies of scale in production. | Kamal Jain, Vijay V. Vazirani, Yinyu Ye |
| 2005 | Limitations of cross-monotonic cost sharing schemes. | Nicole Immorlica, Mohammad Mahdian, Vahab S. Mirrokni |
| 2005 | Marriage, honesty, and stability. | Nicole Immorlica, Mohammad Mahdian |
| 2005 | Approximating vertex cover on dense graphs. | Tomokazu Imamura, Kazuo Iwama |
| 2005 | A categorization theorem on suffix arrays with applications to space efficient text indexes. | Meng He, J. Ian Munro, S. Srinivasa Rao |
| 2005 | Computing minimal triangulations in time O(n | Pinar Heggernes, Jan Arne Telle, Yngve Villanger |
| 2005 | Network design for information networks. | Ara Hayrapetyan, Chaitanya Swamy, va Tardos |
| 2005 | Coupling with the stationary distribution and improved sampling for colorings and independent sets. | Thomas P. Hayes, Eric Vigoda |
| 2005 | Deterministic network coding by matrix completion. | Nicholas J. A. Harvey, David R. Karger, Kazuo Murota |
| 2005 | Unknotting is in AM cup co-AM. | Masao Hara, Seiichi Tani, Makoto Yamamoto |
| 2005 | How fast is the k-means method? | Sariel Har-Peled, Bardia Sadri |
| 2005 | Oblivious routing on node-capacitated and directed graphs. | Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Rcke |