| 2006 | A deterministic subexponential algorithm for solving parity games. | Marcin Jurdzinski, Mike Paterson, Uri Zwick |
| 2006 | An asymptotic approximation algorithm for 3D-strip packing. | Klaus Jansen, Roberto Solis-Oba |
| 2006 | Equilibria for economies with production: constant-returns technologies and production planning constraints. | Kamal Jain, Kasturi R. Varadarajan |
| 2006 | The complexity of matrix completion. | Nicholas J. A. Harvey, David R. Karger, Sergey Yekhanin |
| 2006 | Finding large sticks and potatoes in polygons. | Olaf A. Hall-Holt, Matthew J. Katz, Piyush Kumar, Joseph S. B. Mitchell, Arik Sityon |
| 2006 | New lower bounds for oblivious routing in undirected graphs. | Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton, Harald Rcke |
| 2006 | Improved lower and upper bounds for universal TSP in planar metrics. | Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Frank Thomson Leighton |
| 2006 | The prize-collecting generalized steiner tree problem via a new approach of primal-dual schema. | Mohammad Taghi Hajiaghayi, Kamal Jain |
| 2006 | Approximating unique games. | Anupam Gupta, Kunal Talwar |
| 2006 | Oblivious network design. | Anupam Gupta, Mohammad Taghi Hajiaghayi, Harald Rcke |
| 2006 | Streaming and sublinear approximation of entropy and information distances. | Sudipto Guha, Andrew McGregor, Suresh Venkatasubramanian |
| 2006 | Approximation algorithms for wavelet transform coding of data streams. | Sudipto Guha, Boulos Harb |
| 2006 | Constraint solving via fractional edge covers. | Martin Grohe, Dniel Marx |
| 2006 | Query-efficient algorithms for polynomial interpolation over composites. | Parikshit Gopalan |
| 2006 | The rainbow skip graph: a fault-tolerant constant-degree distributed data structure. | Michael T. Goodrich, Michael J. Nelson, Jonathan Z. Sun |
| 2006 | Rank/select operations on large alphabets: a tool for text indexing. | Alexander Golynski, J. Ian Munro, S. Srinivasa Rao |
| 2006 | Approximating the | Daniel Golovin, Viswanath Nagarajan, Mohit Singh |
| 2006 | Correlation clustering with a fixed number of clusters. | Ioannis Giotis, Venkatesan Guruswami |
| 2006 | Design of data structures for mergeable trees. | Loukas Georgiadis, Robert Endre Tarjan, Renato Fonseca F. Werneck |
| 2006 | Linear programming and unique sink orientations. | Bernd Grtner, Ingo Schurr |
| 2006 | Analysis of incomplete data and an intrinsic-dimension Helly theorem. | Jie Gao, Michael Langberg, Leonard J. Schulman |
| 2006 | Upper degree-constrained partial orientations. | Harold N. Gabow |
| 2006 | Random graphs. | Alan M. Frieze |
| 2006 | Implicit dictionaries with | Gianni Franceschini, J. Ian Munro |
| 2006 | Measure and conquer: a simple O(2 | Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch |