| 2006 | Randomized online algorithms for minimum metric bipartite matching. | Adam Meyerson, Akash Nanavati, Laura J. Poplawski |
| 2006 | Metric cotype. | Manor Mendel, Assaf Naor |
| 2006 | Morphing orthogonal planar graph drawings. | Anna Lubiw, Mark Petrick, Michael J. Spriggs |
| 2006 | A polynomial algorithm to find an independent set of maximum weight in a fork-free graph. | Vadim V. Lozin, Martin Milanic |
| 2006 | FPTAS for mixed-integer polynomial optimization with a fixed number of variables. | Jess A. De Loera, Raymond Hemmecke, Matthias Kppe, Robert Weismantel |
| 2006 | Efficient construction of unit circular-arc models. | Min Chih Lin, Jayme Luiz Szwarcfiter |
| 2006 | A general approach for incremental approximation and hierarchical clustering. | Guolong Lin, Chandrashekhar Nagarajan, Rajmohan Rajaraman, David P. Williamson |
| 2006 | Superiority and complexity of the spaced seeds. | Ming Li, Bin Ma, Louxin Zhang |
| 2006 | Maintaining significant stream statistics over sliding windows. | Lap-Kei Lee, H. F. Ting |
| 2006 | Trees and Markov convexity. | James R. Lee, Assaf Naor, Yuval Peres |
| 2006 | Critical chromatic number and the complexity of perfect packings in graphs. | Daniela Khn, Deryk Osthus |
| 2006 | The price of being near-sighted. | Fabian Kuhn, Thomas Moscibroda, Roger Wattenhofer |
| 2006 | Deterministic boundary recognition and topology extraction for large sensor networks. | Alexander Krller, Sndor P. Fekete, Dennis Pfisterer, Stefan Fischer |
| 2006 | Solving random satisfiable 3CNF formulas in expected polynomial time. | Michael Krivelevich, Dan Vilenchik |
| 2006 | Improved lower bounds for embeddings into | Robert Krauthgamer, Yuval Rabani |
| 2006 | Subgraph characterization of Red/Blue-Split Graph and Knig Egervry Graphs. | Ephraim Korach, Thnh Nguyen, Britta Peis |
| 2006 | A new approach to proving upper bounds for MAX-2-SAT. | Arist Kojevnikov, Alexander S. Kulikov |
| 2006 | A near-tight approximation lower bound and algorithm for the kidnapped robot problem. | Sven Koenig, Apurva Mudgal, Craig A. Tovey |
| 2006 | Anytime algorithms for multi-armed bandit problems. | Robert D. Kleinberg |
| 2006 | Scalable leader election. | Valerie King, Jared Saia, Vishal Sanwalani, Erik Vee |
| 2006 | Generating all vertices of a polyhedron is hard. | Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled M. Elbassioni, Vladimir Gurvich |
| 2006 | Balanced allocation on graphs. | Krishnaram Kenthapadi, Rina Panigrahy |
| 2006 | Max-tolerance graphs as intersection graphs: cliques, cycles, and recognition. | Michael Kaufmann, Jan Kratochvl, Katharina Anna Lehmann, Amarendran Ramaswami Subramanian |
| 2006 | Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting. | Haim Kaplan, Micha Sharir |
| 2006 | Reducing tile complexity for self-assembly through temperature programming. | Ming-Yang Kao, Robert T. Schweller |