| 2007 | A linear work, O(n | Ioannis Koutis, Gary L. Miller |
| 2007 | Dynamic weighted ancestors. | Tsvi Kopelowitz, Moshe Lewenstein |
| 2007 | Optimal scale-free compact routing schemes in networks of low doubling dimension. | Goran Konjevod, Andra W. Richa, Donglin Xia |
| 2007 | Half integral packing, Erdős-Posá-property and graph minors. | Ken-ichi Kawarabayashi |
| 2007 | Noisy binary search and its applications. | Richard M. Karp, Robert Kleinberg |
| 2007 | Polynomial approximation schemes for smoothed and random instances of multidimensional packing problems. | David R. Karger, Krzysztof Onak |
| 2007 | Counting colors in boxes. | Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin |
| 2007 | Games of fixed rank: a hierarchy of bimatrix games. | Ravi Kannan, Thorsten Theobald |
| 2007 | Efficient aggregation algorithms for probabilistic data. | T. S. Jayram, Satyen Kale, Erik Vee |
| 2007 | Ultra-succinct representation of ordered trees. | Jesper Jansson, Kunihiko Sadakane, Wing-Kin Sung |
| 2007 | The independent even factor problem. | Satoru Iwata, Kenjiro Takazawa |
| 2007 | A 1.875: approximation algorithm for the stable marriage problem. | Kazuo Iwama, Shuichi Miyazaki, Naoya Yamauchi |
| 2007 | A near linear time constant factor approximation for Euclidean bichromatic matching (cost). | Piotr Indyk |
| 2007 | Digraph measures: Kelly decompositions, games, and orderings. | Paul Hunter, Stephan Kreutzer |
| 2007 | Maximum | Jan M. Hochstein, Karsten Weihe |
| 2007 | Combinatorial algorithms for web search engines: three success stories. | Monika Henzinger |
| 2007 | An algebraic algorithm for weighted linear matroid intersection. | Nicholas J. A. Harvey |
| 2007 | Efficient algorithms for computing all low | Ramesh Hariharan, Telikepalli Kavitha, Debmalya Panigrahi |
| 2007 | Improved bounds for the symmetric rendezvous value on the line. | Qiaoming Han, Donglei Du, Juan Carlos Vera, Luis Fernando Zuluaga |
| 2007 | Semi-oblivious routing: lower bounds. | Mohammad Taghi Hajiaghayi, Robert Kleinberg, Tom Leighton |
| 2007 | An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem. | Anupam Gupta, Jochen Knemann, Stefano Leonardi, R. Ravi, Guido Schfer |
| 2007 | Reconstruction using witness complexes. | Leonidas J. Guibas, Steve Oudot |
| 2007 | Model-driven optimization using adaptive probes. | Sudipto Guha, Kamesh Munagala |
| 2007 | Estimating the sortedness of a data stream. | Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, Ravi Kumar |
| 2007 | Optimal dynamic vertical ray shooting in rectilinear planar subdivisions. | Yoav Giyora, Haim Kaplan |