| 2006 | A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains. James King |
| 2006 | A Faster Algorithm for Finding Maximum Independent Sets in Sparse Graphs. Martin Fürer |
| 2006 | A New GCD Algorithm for Quadratic Number Rings with Unique Factorization. Saurabh Agarwal, Gudmund Skovbjerg Frandsen |
| 2006 | A Parallel Algorithm for Finding All Successive Minimal Maximum Subsequences. Ho-Kwok Dai, Hung-Chi Su |
| 2006 | Algorithmic Challenges in Web Search Engines. Ricardo A. Baeza-Yates |
| 2006 | Algorithms for Modular Counting of Roots of Multivariate Polynomials. Parikshit Gopalan, Venkatesan Guruswami, Richard J. Lipton |
| 2006 | An Algorithm for a Generalized Maximum Subsequence Problem. Thorsten Bernholt, Thomas Hofmeister |
| 2006 | An Architecture for Provably Secure Computation. Miklós Ajtai, Cynthia Dwork, Larry J. Stockmeyer |
| 2006 | An Efficient Approximation Algorithm for Point Pattern Matching Under Noise. Vicky Choi, Navin Goyal |
| 2006 | An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees. Boaz Ben-Moshe, Binay K. Bhattacharya, Qiaosheng Shi |
| 2006 | Approximate Sorting. Joachim Giesen, Eva Schuberth, Milos Stojakovic |
| 2006 | Asynchronous Behavior of Double-Quiescent Elementary Cellular Automata. Nazim Fatès, Damien Regnault, Nicolas Schabanel, Eric Thierry |
| 2006 | C-Varieties, Actions and Wreath Product. Laura Chaubard |
| 2006 | Classical Computability and Fuzzy Turing Machines. Benjamín René Callejas Bedregal, Santiago Figueira |
| 2006 | Common Deadline Lazy Bureaucrat Scheduling Revisited. Ling Gai, Guochuan Zhang |
| 2006 | Competitive Analysis of Scheduling Algorithms for Aggregated Links. Wojciech Jawor, Marek Chrobak, Christoph Dürr |
| 2006 | Connected Treewidth and Connected Graph Searching. Pierre Fraigniaud, Nicolas Nisse |
| 2006 | Constructions of Approximately Mutually Unbiased Bases. Igor E. Shparlinski, Arne Winterhof |
| 2006 | Counting Proportions of Sets: Expressive Power with Almost Order. Argimiro Arratia, Carlos E. Ortiz |
| 2006 | Customized Newspaper Broadcast: Data Broadcast with Dependencies. Sandeep Dey, Nicolas Schabanel |
| 2006 | Cut Problems in Graphs with a Budget Constraint. Roee Engelberg, Jochen Könemann, Stefano Leonardi, Joseph Naor |
| 2006 | Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams. Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, Michiel H. M. Smid |
| 2006 | De Dictionariis Dynamicis Pauco Spatio Utentibus ( Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Patrascu |
| 2006 | Design and Analysis of Online Batching Systems. Regant Y. S. Hung, Hing-Fung Ting |
| 2006 | Efficient Approximate Dictionary Look-Up for Long Words over Small Alphabets. Abdullah N. Arslan |
| 2006 | Efficient Computation of the Relative Entropy of Probabilistic Automata. Corinna Cortes, Mehryar Mohri, Ashish Rastogi, Michael Riley |
| 2006 | Eliminating Cycles in the Discrete Torus. Béla Bollobás, Guy Kindler, Imre Leader, Ryan O'Donnell |
| 2006 | Exponential Lower Bounds on the Space Complexity of OBDD-Based Graph Algorithms. Daniel Sawitzki |
| 2006 | Finding All Minimal Infrequent Multi-dimensional Intervals. Khaled M. Elbassioni |
| 2006 | Hardness Amplification Via Space-Efficient Direct Products. Venkatesan Guruswami, Valentine Kabanets |
| 2006 | I/O-Efficient Algorithms on Near-Planar Graphs. Herman J. Haverkort, Laura Toma |
| 2006 | Improved Exponential-Time Algorithms for Treewidth and Minimum Fill-In. Yngve Villanger |
| 2006 | LATIN 2006: Theoretical Informatics, 7th Latin American Symposium, Valdivia, Chile, March 20-24, 2006, Proceedings José R. Correa, Alejandro Hevia, Marcos A. Kiwi |
| 2006 | Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges. Edgar Chávez, Stefan Dobrev, Evangelos Kranakis, Jaroslav Opatrny, Ladislav Stacho, Jorge Urrutia |
| 2006 | Lossless Data Compression Via Error Correction. Sergio Verdú |
| 2006 | Lower Bounds for Clear Transmissions in Radio Networks. Martin Farach-Colton, Rohan J. Fernandes, Miguel A. Mosteiro |
| 2006 | Lower Bounds for Geometric Diameter Problems. Hervé Fournier, Antoine Vigneron |
| 2006 | Matching Based Augmentations for Approximating Connectivity Problems. R. Ravi |
| 2006 | Maximizing Throughput in Queueing Networks with Limited Flexibility. Douglas G. Down, George Karakostas |
| 2006 | Minimal Eulerian Circuit in a Labeled Digraph. Eduardo Moreno, Martín Matamala |
| 2006 | Minimal Split Completions of Graphs. Pinar Heggernes, Federico Mancini |
| 2006 | Minimum Cost Source Location Problems with Flow Requirements. Mariko Sakashita, Kazuhisa Makino, Satoru Fujishige |
| 2006 | Mobile Agent Rendezvous in a Synchronous Torus. Evangelos Kranakis, Danny Krizanc, Euripides Markou |
| 2006 | Modelling Errors and Recovery for Communication. Madhu Sudan |
| 2006 | Network Flow Spanners. Feodor F. Dragan, Chenyu Yan |
| 2006 | Oblivious Medians Via Online Bidding. Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young |
| 2006 | On Behalf of the Seller and Society: Bicriteria Mechanisms for Unit-Demand Auctions. Claudson F. Bornstein, Eduardo Sany Laber, Marcelo Mas |
| 2006 | On Clusters in Markov Chains. Nir Ailon, Steve Chien, Cynthia Dwork |
| 2006 | On Minimum Gabriele Di Stefano, Stefan Krause, Marco E. Lübbecke, Uwe T. Zimmermann |
| 2006 | On Sampling in Higher-Dimensional Peer-to-Peer Systems. Goran Konjevod, Andréa W. Richa, Donglin Xia |
| 2006 | Optimally Adaptive Integration of Univariate Lipschitz Functions. Ilya Baran, Erik D. Demaine, Dmitriy A. Katz |
| 2006 | Packing Dicycle Covers in Planar Graphs with No Orlando Lee, Aaron Williams |
| 2006 | Pattern Matching Statistics on Correlated Sources. Jérémie Bourdon, Brigitte Vallée |
| 2006 | Position-Restricted Substring Searching. Veli Mäkinen, Gonzalo Navarro |
| 2006 | RISOTTO: Fast Extraction of Motifs with Mismatches. Nadia Pisanti, Alexandra M. Carvalho, Laurent Marsan, Marie-France Sagot |
| 2006 | RNA Molecules: Glimpses Through an Algorithmic Lens. Anne Condon |
| 2006 | Random Bichromatic Matchings. Nayantara Bhatnagar, Dana Randall, Vijay V. Vazirani, Eric Vigoda |
| 2006 | Randomly Colouring Graphs with Girth Five and Large Maximum Degree. Lap Chi Lau, Michael Molloy |
| 2006 | Reconfigurations in Graphs and Grids. Gruia Calinescu, Adrian Dumitrescu, János Pach |
| 2006 | Rectilinear Approximation of a Set of Points in the Plane. Yan Mayster, Mario Alberto López |
| 2006 | Relations Among Notions of Security for Identity Based Encryption Schemes. Nuttapong Attrapadung, Yang Cui, David Galindo, Goichiro Hanaoka, Ichiro Hasuo, Hideki Imai, Kanta Matsuura, Peng Yang, Rui Zhang |
| 2006 | Robust Model-Checking of Linear-Time Properties in Timed Automata. Patricia Bouyer, Nicolas Markey, Pierre-Alain Reynier |
| 2006 | Scoring Matrices That Induce Metrics on Sequences. Elói Araújo, José Soares |
| 2006 | Sharp Estimates for the Main Parameters of the Euclid Algorithm. Loïck Lhote, Brigitte Vallée |
| 2006 | Speeding up Approximation Algorithms for NP-Hard Spanning Forest Problems by Multi-objective Optimization. Frank Neumann, Marco Laumanns |
| 2006 | Squares. Ferran Hurtado |
| 2006 | Stochastic Covering and Adaptivity. Michel X. Goemans, Jan Vondrák |
| 2006 | The Branch-Width of Circular-Arc Graphs. Frédéric Mazoit |
| 2006 | The Committee Decision Problem. Eli Gafni, Sergio Rajsbaum, Michel Raynal, Corentin Travers |
| 2006 | The Complexity of Diffuse Reflections in a Simple Polygon. Boris Aronov, Alan R. Davis, John Iacono, Albert Siu Cheong Yu |
| 2006 | The Computational Complexity of the Parallel Knock-Out Problem. Hajo Broersma, Matthew Johnson, Daniël Paulusma, Iain A. Stewart |
| 2006 | The Online Freeze-Tag Problem. Mikael Hammar, Bengt J. Nilsson, Mia Persson |
| 2006 | The Power and Weakness of Randomness in Computation. Avi Wigderson |
| 2006 | Two Birds with One Stone: The Best of Branchwidth and Treewidth with One Algorithm. Frederic Dorn, Jan Arne Telle |