| 2006 | A Combinatorial Approach to Collapsing Words. | Alessandra Cherubini, Pawel Gawrychowski, Andrzej Kisielewicz, Brunetto Piochi |
| 2006 | Improved Parameterized Upper Bounds for Vertex Cover. | Jianer Chen, Iyad A. Kanj, Ge Xia |
| 2006 | On Comparing Sums of Square Roots of Small Integers. | Qi Cheng |
| 2006 | On the Repetition Threshold for Large Alphabets. | Arturo Carpi |
| 2006 | The Kleene Equality for Graphs. | Arnaud Carayol, Didier Caucal |
| 2006 | Coloring Random 3-Colorable Graphs with Non-uniform Edge Probabilities. | Ulrik Brandes, Jrgen Lerner |
| 2006 | On the Complexity of Limit Sets of Cellular Automata Associated with Probability Measures. | Laurent Boyer, Victor Poupet, Guillaume Theyssier |
| 2006 | Concrete Multiplicative Complexity of Symmetric Functions. | Joan Boyar, Ren Peralta |
| 2006 | Equations on Partial Words. | Francine Blanchet-Sadri, D. Dakota Blair, Rebeca V. Lewis |
| 2006 | Crochemore Factorization of Sturmian and Other Infinite Words. | Jean Berstel, Alessandra Savelli |
| 2006 | The Multiparty Communication Complexity of Exact- | Richard Beigel, William I. Gasarch, James Glenn |
| 2006 | A Polynomial Time Nilpotence Test for Galois Groups and Related Results. | Vikraman Arvind, Piyush P. Kurur |
| 2006 | Algebraic Characterizations of Unitary Linear Quantum Cellular Automata. | Pablo Arrighi |
| 2006 | A Unified Construction of the Glushkov, Follow, and Antimirov Automata. | Cyril Allauzen, Mehryar Mohri |
| 2006 | Approximate Shortest Path Queries on Weighted Polyhedral Surfaces. | Lyudmil Aleksandrov, Hristo N. Djidjev, Hua Guo, Anil Maheshwari, Doron Nussbaum, Jrg-Rdiger Sack |
| 2006 | Decompositions, Partitions, and Coverings with Convex Polygons and Pseudo-triangles. | Oswin Aichholzer, Clemens Huemer, Sarah Kappes, Bettina Speckmann, Csaba D. Tth |
| 2005 | An Invitation to Play. | Wieslaw Zielonka |
| 2005 | On the Communication Complexity of Co-linearity Problems. | Andrew Chi-Chih Yao |
| 2005 | Stratified Boolean Grammars. | Michal Wrona |
| 2005 | Explicit Inapproximability Bounds for the Shortest Superstring Problem. | Virginia Vassilevska |
| 2005 | On Small Hard Leaf Languages. | Falk Unger |
| 2005 | The Generalization of Dirac's Theorem for Hypergraphs. | Endre Szemerdi, Andrzej Rucinski, Vojtech Rdl |
| 2005 | On Beta-Shifts Having Arithmetical Languages. | Jakob Grue Simonsen |
| 2005 | D-Width: A More Natural Measure for Directed Tree Width. | Mohammad Ali Safari |
| 2005 | An Exact 2.9416 | Tobias Riege, Jrg Rothe |