| 2006 | Kolmogorov Complexity with Error. | Lance Fortnow, Troy Lee, Nikolai K. Vereshchagin |
| 2006 | Linear Advice for Randomized Logarithmic Space. | Lance Fortnow, Adam R. Klivans |
| 2006 | The Ubiquitous Digital Tree. | Philippe Flajolet |
| 2006 | On the Accepting Power of 2-Tape Bchi Automata. | Olivier Finkel |
| 2006 | External String Sorting: Faster and Cache-Oblivious. | Rolf Fagerberg, Anna Pagh, Rasmus Pagh |
| 2006 | Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games. | Kousha Etessami, Mihalis Yannakakis |
| 2006 | Nested Pebbles and Transitive Closure. | Joost Engelfriet, Hendrik Jan Hoogeboom |
| 2006 | Conflict-Free Colorings of Rectangles Ranges. | Khaled M. Elbassioni, Nabil H. Mustafa |
| 2006 | Tradeoffs in Depth-Two Superconcentrators. | Chinmoy Dutta, Jaikumar Radhakrishnan |
| 2006 | Generating Randomized Roundings with Cardinality Constraints and Derandomizations. | Benjamin Doerr |
| 2006 | Fast FPT-Algorithms for Cleaning Grids. | Josep Daz, Dimitrios M. Thilikos |
| 2006 | Grid Vertex-Unfolding Orthogonal Polyhedra. | Mirela Damian, Robin Y. Flatland, Joseph O'Rourke |
| 2006 | Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements. | Reuven Cohen, David Peleg |
| 2006 | Convergence and Approximation in Potential Games. | George Christodoulou, Vahab S. Mirrokni, Anastasios Sidiropoulos |
| 2006 | Markov Decision Processes with Multiple Objectives. | Krishnendu Chatterjee, Rupak Majumdar, Thomas A. Henzinger |
| 2006 | Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games. | Krishnendu Chatterjee, Thomas A. Henzinger |
| 2006 | Estimating Entropy and Entropy Norm on Data Streams. | Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan |
| 2006 | Oblivious Symmetric Alternation. | Venkatesan T. Chakaravarthy, Sambuddha Roy |
| 2006 | Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds. | Harry Buhrman, Leen Torenvliet, Falk Unger |
| 2006 | Datalog and Constraint Satisfaction with Infinite Templates. | Manuel Bodirsky, Vctor Dalmau |
| 2006 | Amortized Rigidness in Dynamic Cartesian Trees. | Iwona Bialynicka-Birula, Roberto Grossi |
| 2006 | DAG-Width and Parity Games. | Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer |
| 2006 | Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes. | Ahmed A. Belal, Amr Elmasry |
| 2006 | Complete Codes in a Sofic Shift. | Marie-Pierre Bal, Dominique Perrin |
| 2006 | Generalized Modal Satisfiability. | Michael Bauland, Edith Hemaspaandra, Henning Schnoor, Ilka Schnoor |