| 2006 | A Combinatorial Approach to Collapsing Words. Alessandra Cherubini, Pawel Gawrychowski, Andrzej Kisielewicz, Brunetto Piochi |
| 2006 | A Core Calculus for Scala Type Checking. Vincent Cremet, François Garillot, Sergueï Lenglet, Martin Odersky |
| 2006 | A Polynomial Time Nilpotence Test for Galois Groups and Related Results. Vikraman Arvind, Piyush P. Kurur |
| 2006 | A Reachability Algorithm for General Petri Nets Based on Transition Invariants. Alexander E. Kostin |
| 2006 | A Unified Construction of the Glushkov, Follow, and Antimirov Automata. Cyril Allauzen, Mehryar Mohri |
| 2006 | Algebraic Characterizations of Unitary Linear Quantum Cellular Automata. Pablo Arrighi |
| 2006 | An Efficient Algorithm Finds Noticeable Trends and Examples Concerning the Cerny Conjecture. A. N. Trahtman |
| 2006 | An Expressive Temporal Logic for Real Time. Yoram Hirshfeld, Alexander Moshe Rabinovich |
| 2006 | Approximability of Bounded Occurrence Max Ones. Fredrik Kuivinen |
| 2006 | Approximate Shortest Path Queries on Weighted Polyhedral Surfaces. Lyudmil Aleksandrov, Hristo N. Djidjev, Hua Guo, Anil Maheshwari, Doron Nussbaum, Jörg-Rüdiger Sack |
| 2006 | Approximation Algorithms and Hardness Results for Labeled Connectivity Problems. Refael Hassin, Jérôme Monnot, Danny Segev |
| 2006 | Characterizing Valiant's Algebraic Complexity Classes. Guillaume Malod, Natacha Portier |
| 2006 | Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities. Ulrik Brandes, Jürgen Lerner |
| 2006 | Completeness of Global Evaluation Logic. Sergey Goncharov, Lutz Schröder, Till Mossakowski |
| 2006 | Concrete Multiplicative Complexity of Symmetric Functions. Joan Boyar, René Peralta |
| 2006 | Constrained Minimum Enclosing Circle with Center on a Query Line Segment. Sasanka Roy, Arindam Karmakar, Sandip Das, Subhas C. Nandy |
| 2006 | Crochemore Factorization of Sturmian and Other Infinite Words. Jean Berstel, Alessandra Savelli |
| 2006 | Decompositions, Partitions, and Coverings with Convex Polygons and Pseudo-triangles. Oswin Aichholzer, Clemens Huemer, Sarah Kappes, Bettina Speckmann, Csaba D. Tóth |
| 2006 | Dimension Characterizations of Complexity Classes. Xiaoyang Gu, Jack H. Lutz |
| 2006 | Distributed Data Structures: A Survey on Informative Labeling Schemes. Cyril Gavoille |
| 2006 | Equations on Partial Words. Francine Blanchet-Sadri, D. Dakota Blair, Rebeca V. Lewis |
| 2006 | Fast Iterative Arrays with Restricted Inter-cell Communication: Constructions and Decidability. Martin Kutrib, Andreas Malcher |
| 2006 | Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes. Slawomir Lasota, Wojciech Rytter |
| 2006 | From Deduction Graphs to Proof Nets: Boxes and Sharing in the Graphical Presentation of Deductions. Herman Geuvers, Iris Loeb |
| 2006 | From Three Ideas in TCS to Three Applications in Bioinformatics. Ming Li |
| 2006 | Generalised Integer Programming Based on Logically Defined Relations. Peter Jonsson, Gustav Nordh |
| 2006 | Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners. Christopher M. Homan, Lane A. Hemaspaandra |
| 2006 | Hierarchical Unambiguity. Holger Spakowski, Rahul Tripathi |
| 2006 | Improved Parameterized Upper Bounds for Vertex Cover. Jianer Chen, Iyad A. Kanj, Ge Xia |
| 2006 | Learning Bayesian Networks Does Not Have to Be NP-Hard. Norbert Dojer |
| 2006 | Lempel-Ziv Dimension for Lempel-Ziv Compression. María López-Valdés |
| 2006 | Lower Bounds for the Transition Complexity of NFAs. Michael Domaratzki, Kai Salomaa |
| 2006 | Machines that Can Output Empty Words. Christian Glaßer, Stephen D. Travers |
| 2006 | Magic Numbers in the State Hierarchy of Finite Automata. Viliam Geffert |
| 2006 | Mathematical Foundations of Computer Science 2006, 31st International Symposium, MFCS 2006, Stará Lesná, Slovakia, August 28-September 1, 2006, Proceedings Rastislav Kralovic, Pawel Urzyczyn |
| 2006 | Minimal Chordal Sense of Direction and Circulant Graphs. Rodrigo S. C. Leão, Valmir Carneiro Barbosa |
| 2006 | Multicast Transmissions in Non-cooperative Networks with a Limited Number of Selfish Moves. Angelo Fanelli, Michele Flammini, Giovanna Melideo, Luca Moscardelli |
| 2006 | NOF-Multiparty Information Complexity Bounds for Pointer Jumping. André Gronemeier |
| 2006 | Non-cooperative Tree Creation. Martin Hoefer |
| 2006 | On Comparing Sums of Square Roots of Small Integers. Qi Cheng |
| 2006 | On Genome Evolution with Innovation. Damian Wójtowicz, Jerzy Tiuryn |
| 2006 | On Matroid Representability and Minor Problems. Petr Hlinený |
| 2006 | On Non-Interactive Zero-Knowledge Proofs of Knowledge in the Shared Random String Model. Giuseppe Persiano, Ivan Visconti |
| 2006 | On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures. Laurent Boyer, Victor Poupet, Guillaume Theyssier |
| 2006 | On the Correlation Between Parity and Modular Polynomials. Anna Gál, Vladimir Trifonov |
| 2006 | On the Repetition Threshold for Large Alphabets. Arturo Carpi |
| 2006 | On the Representation of Kleene Algebras with Tests. Dexter Kozen |
| 2006 | Online Single Machine Batch Scheduling. Beat Gfeller, Leon Peeters, Birgitta Weber, Peter Widmayer |
| 2006 | Optimal Linear Arrangement of Interval Graphs. Johanne Cohen, Fedor V. Fomin, Pinar Heggernes, Dieter Kratsch, Gregory Kucherov |
| 2006 | Optimally Fast Data Gathering in Sensor Networks. Luisa Gargano, Adele A. Rescigno |
| 2006 | Partially Commutative Inverse Monoids. Volker Diekert, Markus Lohrey, Alexander Miller |
| 2006 | Probabilistic Length-Reducing Automata. Tomasz Jurdzinski |
| 2006 | Quantum Weakly Nondeterministic Communication Complexity. François Le Gall |
| 2006 | Querying and Embedding Compressed Texts. Yury Lifshits, Markus Lohrey |
| 2006 | Reductions for Monotone Boolean Circuits. Kazuo Iwama, Hiroki Morizumi |
| 2006 | Smart Robot Teams Exploring Sparse Trees. Miroslaw Dynia, Jaroslaw Kutylowski, Friedhelm Meyer auf der Heide, Christian Schindelhauer |
| 2006 | Sorting Long Sequences in a Single Hop Radio Network. Marcin Kik |
| 2006 | Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture. Ondrej Klíma, Benoît Larose, Pascal Tesson |
| 2006 | The Complexity of Counting Functions with Easy Decision Version. Aris Pagourtzis, Stathis Zachos |
| 2006 | The Data Complexity of MDatalog in Basic Modal Logics. Linh Anh Nguyen |
| 2006 | The Kleene Equality for Graphs. Arnaud Carayol, Didier Caucal |
| 2006 | The Lempel-Ziv Complexity of Fixed Points of Morphisms. Sorin Constantinescu, Lucian Ilie |
| 2006 | The Multiparty Communication Complexity of Exact- Richard Beigel, William I. Gasarch, James Glenn |
| 2006 | The Price of Defense. Marios Mavronicolas, Loizos Michael, Vicky G. Papadopoulou, Anna Philippou, Paul G. Spirakis |
| 2006 | The Structure of Tractable Constraint Satisfaction Problems. Martin Grohe |
| 2006 | Toward the Eigenvalue Power Law. Robert Elsässer |
| 2006 | Tree Exploration with an Oracle. Pierre Fraigniaud, David Ilcinkas, Andrzej Pelc |
| 2006 | Valiant's Model: From Exponential Sums to Exponential Products. Pascal Koiran, Sylvain Perifel |
| 2006 | Very Sparse Leaf Languages. Lance Fortnow, Mitsunori Ogihara |