| 2006 | A Faster Algorithm for the Steiner Tree Problem. Daniel Mölle, Stefan Richter, Peter Rossmanith |
| 2006 | Amortized Rigidness in Dynamic Cartesian Trees. Iwona Bialynicka-Birula, Roberto Grossi |
| 2006 | Combining Multiple Heuristics. Tzur Sayag, Shai Fine, Yishay Mansour |
| 2006 | Complete Codes in a Sofic Shift. Marie-Pierre Béal, Dominique Perrin |
| 2006 | Conflict-Free Colorings of Rectangles Ranges. Khaled M. Elbassioni, Nabil H. Mustafa |
| 2006 | Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two. Alexander Healy, Emanuele Viola |
| 2006 | Convergence and Approximation in Potential Games. George Christodoulou, Vahab S. Mirrokni, Anastasios Sidiropoulos |
| 2006 | Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements. Reuven Cohen, David Peleg |
| 2006 | DAG-Width and Parity Games. Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer |
| 2006 | Datalog and Constraint Satisfaction with Infinite Templates. Manuel Bodirsky, Víctor Dalmau |
| 2006 | Definability of Languages by Generalized First-Order Formulas over (N, +). Amitabha Roy, Howard Straubing |
| 2006 | Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes. Ahmed A. Belal, Amr Elmasry |
| 2006 | Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games. Kousha Etessami, Mihalis Yannakakis |
| 2006 | Energy-Efficient Algorithms for Flow Time Minimization. Susanne Albers, Hiroshi Fujiwara |
| 2006 | Entanglement in Interactive Proof Systems with Binary Answers. Stephanie Wehner |
| 2006 | Equivalence of F-Algebras and Cubic Forms. Manindra Agrawal, Nitin Saxena |
| 2006 | Estimating Entropy and Entropy Norm on Data Streams. Amit Chakrabarti, Khanh Do Ba, S. Muthukrishnan |
| 2006 | Evaluating Monotone Circuits on Cylinders, Planes and Tori. Nutan Limaye, Meena Mahajan, Jayalal Sarma |
| 2006 | Exact Price of Anarchy for Polynomial Congestion Games. Sebastian Aland, Dominic Dumrauf, Martin Gairing, Burkhard Monien, Florian Schoppmann |
| 2006 | External String Sorting: Faster and Cache-Oblivious. Rolf Fagerberg, Anna Pagh, Rasmus Pagh |
| 2006 | Fast FPT-Algorithms for Cleaning Grids. Josep Díaz, Dimitrios M. Thilikos |
| 2006 | Flat Holonomies on Automata Networks. Gene Itkis, Leonid A. Levin |
| 2006 | Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences. Andrey Yu. Rumyantsev, M. A. Ushakov |
| 2006 | Generalized Modal Satisfiability. Michael Bauland, Edith Hemaspaandra, Henning Schnoor, Ilka Schnoor |
| 2006 | Generating Randomized Roundings with Cardinality Constraints and Derandomizations. Benjamin Doerr |
| 2006 | Grid Vertex-Unfolding Orthogonal Polyhedra. Mirela Damian, Robin Y. Flatland, Joseph O'Rourke |
| 2006 | Interprocedurally Analyzing Polynomial Identities. Markus Müller-Olm, Michael Petter, Helmut Seidl |
| 2006 | Invariants of Automatic Presentations and Semi-synchronous Transductions. Vince Bárány |
| 2006 | Kolmogorov Complexity and the Recursion Theorem. Bjørn Kjos-Hanssen, Wolfgang Merkle, Frank Stephan |
| 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 | Markov Decision Processes with Multiple Objectives. Krishnendu Chatterjee, Rupak Majumdar, Thomas A. Henzinger |
| 2006 | Memoryless Facility Location in One Pass. Dimitris Fotakis |
| 2006 | Nested Pebbles and Transitive Closure. Joost Engelfriet, Hendrik Jan Hoogeboom |
| 2006 | Oblivious Symmetric Alternation. Venkatesan T. Chakaravarthy, Sambuddha Roy |
| 2006 | On Critical Exponents in Fixed Points of Binary Dalia Krieger |
| 2006 | On Hypergraph and Graph Isomorphism with Bounded Color Classes. Vikraman Arvind, Johannes Köbler |
| 2006 | On the Accepting Power of 2-Tape Büchi Automata. Olivier Finkel |
| 2006 | On the Complexity of the "Most General" Firing Squad Synchronization Problem. Darin Goldstein, Kojiro Kobayashi |
| 2006 | Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. John M. Hitchcock |
| 2006 | Online Sorting Buffers on Line. Rohit Khandekar, Vinayaka Pandit |
| 2006 | Optimal Node Routing. Yossi Azar, Yoel Chaiutin |
| 2006 | Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems. Daniel Golovin, Vineet Goyal, R. Ravi |
| 2006 | Quantum Algorithms for Matching and Network Flows. Andris Ambainis, Robert Spalek |
| 2006 | Redundancy in Complete Sets. Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang |
| 2006 | Regular Expressions and NFAs Without Georg Schnitger |
| 2006 | Regularity Problems for Visibly Pushdown Languages. Vince Bárány, Christof Löding, Olivier Serre |
| 2006 | Reliable Computations Based on Locally Decodable Codes. Andrei Romashchenko |
| 2006 | STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings Bruno Durand, Wolfgang Thomas |
| 2006 | Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds. Harry Buhrman, Leen Torenvliet, Falk Unger |
| 2006 | Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games. Krishnendu Chatterjee, Thomas A. Henzinger |
| 2006 | The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms. Paolo Penna, Carmine Ventre |
| 2006 | The Number of Runs in a String: Improved Analysis of the Linear Upper Bound. Wojciech Rytter |
| 2006 | The Ubiquitous Digital Tree. Philippe Flajolet |
| 2006 | Theory and Application of Width Bounded Geometric Separator. Bin Fu |
| 2006 | Tradeoffs in Depth-Two Superconcentrators. Chinmoy Dutta, Jaikumar Radhakrishnan |
| 2006 | Weighted Asynchronous Cellular Automata. Dietrich Kuske |
| 2006 | Weighted Picture Automata and Weighted Logics. Ina Mäurer |