| 2006 | Constrained Minimum Enclosing Circle with Center on a Query Line Segment. | Sasanka Roy, Arindam Karmakar, Sandip Das, Subhas C. Nandy |
| 2006 | On Non-Interactive Zero-Knowledge Proofs of Knowledge in the Shared Random String Model. | Giuseppe Persiano, Ivan Visconti |
| 2006 | The Complexity of Counting Functions with Easy Decision Version. | Aris Pagourtzis, Stathis Zachos |
| 2006 | Untitled record | Wael El Oraiby, Dominique Schmitt |
| 2006 | The Data Complexity of MDatalog in Basic Modal Logics. | Linh Anh Nguyen |
| 2006 | The Price of Defense. | Marios Mavronicolas, Loizos Michael, Vicky G. Papadopoulou, Anna Philippou, Paul G. Spirakis |
| 2006 | Characterizing Valiant's Algebraic Complexity Classes. | Guillaume Malod, Natacha Portier |
| 2006 | Lempel-Ziv Dimension for Lempel-Ziv Compression. | Mara Lpez-Valds |
| 2006 | Querying and Embedding Compressed Texts. | Yury Lifshits, Markus Lohrey |
| 2006 | From Three Ideas in TCS to Three Applications in Bioinformatics. | Ming Li |
| 2006 | Minimal Chordal Sense of Direction and Circulant Graphs. | Rodrigo S. C. Leo, Valmir Carneiro Barbosa |
| 2006 | Faster Algorithm for Bisimulation Equivalence of Normed Context-Free Processes. | Slawomir Lasota, Wojciech Rytter |
| 2006 | Fast Iterative Arrays with Restricted Inter-cell Communication: Constructions and Decidability. | Martin Kutrib, Andreas Malcher |
| 2006 | Approximability of Bounded Occurrence Max Ones. | Fredrik Kuivinen |
| 2006 | On the Representation of Kleene Algebras with Tests. | Dexter Kozen |
| 2006 | A Reachability Algorithm for General Petri Nets Based on Transition Invariants. | Alexander E. Kostin |
| 2006 | Valiant's Model: From Exponential Sums to Exponential Products. | Pascal Koiran, Sylvain Perifel |
| 2006 | Systems of Equations over Finite Semigroups and the #CSP Dichotomy Conjecture. | Ondrej Klma, Benot Larose, Pascal Tesson |
| 2006 | Sorting Long Sequences in a Single Hop Radio Network. | Marcin Kik |
| 2006 | Probabilistic Length-Reducing Automata. | Tomasz Jurdzinski |
| 2006 | Generalised Integer Programming Based on Logically Defined Relations. | Peter Jonsson, Gustav Nordh |
| 2006 | Reductions for Monotone Boolean Circuits. | Kazuo Iwama, Hiroki Morizumi |
| 2006 | Guarantees for the Success Frequency of an Algorithm for Finding Dodgson-Election Winners. | Christopher M. Homan, Lane A. Hemaspaandra |
| 2006 | Non-cooperative Tree Creation. | Martin Hoefer |
| 2006 | On Matroid Representability and Minor Problems. | Petr Hlinen |