| 2006 | Design and Analysis of Online Batching Systems. | Regant Y. S. Hung, Hing-Fung Ting |
| 2006 | Minimal Split Completions of Graphs. | Pinar Heggernes, Federico Mancini |
| 2006 | I/O-Efficient Algorithms on Near-Planar Graphs. | Herman J. Haverkort, Laura Toma |
| 2006 | The Online Freeze-Tag Problem. | Mikael Hammar, Bengt J. Nilsson, Mia Persson |
| 2006 | Hardness Amplification Via Space-Efficient Direct Products. | Venkatesan Guruswami, Valentine Kabanets |
| 2006 | Algorithms for Modular Counting of Roots of Multivariate Polynomials. | Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton |
| 2006 | Stochastic Covering and Adaptivity. | Michel X. Goemans, Jan Vondrk |
| 2006 | Approximate Sorting. | Joachim Giesen, Eva Schuberth, Milos Stojakovic |
| 2006 | Common Deadline Lazy Bureaucrat Scheduling Revisited. | Ling Gai, Guochuan Zhang |
| 2006 | The Committee Decision Problem. | Eli Gafni, Sergio Rajsbaum, Michel Raynal, Corentin Travers |
| 2006 | A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs. | Martin Frer |
| 2006 | Connected Treewidth and Connected Graph Searching. | Pierre Fraigniaud, Nicolas Nisse |
| 2006 | Lower Bounds for Geometric Diameter Problems. | Herv Fournier, Antoine Vigneron |
| 2006 | Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata. | Nazim Fats, Damien Regnault, Nicolas Schabanel, Eric Thierry |
| 2006 | Lower Bounds for Clear Transmissions in Radio Networks. | Martin Farach-Colton, Rohan J. Fernandes, Miguel A. Mosteiro |
| 2006 | Cut Problems in Graphs with a Budget Constraint. | Roee Engelberg, Jochen Knemann, Stefano Leonardi, Joseph Naor |
| 2006 | Finding All Minimal Infrequent Multi-dimensional Intervals. | Khaled M. Elbassioni |
| 2006 | Network Flow Spanners. | Feodor F. Dragan, Chenyu Yan |
| 2006 | Maximizing Throughput in Queueing Networks with Limited Flexibility. | Douglas G. Down, George Karakostas |
| 2006 | Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm. | Frederic Dorn, Jan Arne Telle |
| 2006 | Customized Newspaper Broadcast: Data Broadcast with Dependencies. | Sandeep Dey, Nicolas Schabanel |
| 2006 | De Dictionariis Dynamicis Pauco Spatio Utentibus ( | Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Patrascu |
| 2006 | A Parallel Algorithm for Finding All Successive Minimal Maximum Subsequences. | Ho-Kwok Dai, Hung-Chi Su |
| 2006 | Efficient Computation of the Relative Entropy of Probabilistic Automata. | Corinna Cortes, Mehryar Mohri, Ashish Rastogi, Michael Riley |
| 2006 | RNA Molecules: Glimpses Through an Algorithmic Lens. | Anne Condon |