| 2006 | Oblivious Medians Via Online Bidding. | Marek Chrobak, Claire Kenyon, John Noga, Neal E. Young |
| 2006 | An Efficient Approximation Algorithm for Point Pattern Matching Under Noise. | Vicky Choi, Navin Goyal |
| 2006 | Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges. | Edgar Chvez, Stefan Dobrev, Evangelos Kranakis, Jaroslav Opatrny, Ladislav Stacho, Jorge Urrutia |
| 2006 | C-Varieties, Actions and Wreath Product. | Laura Chaubard |
| 2006 | Reconfigurations in Graphs and Grids. | Gruia Calinescu, Adrian Dumitrescu, Jnos Pach |
| 2006 | The Computational Complexity of the Parallel Knock-Out Problem. | Hajo Broersma, Matthew Johnson, Danil Paulusma, Iain A. Stewart |
| 2006 | Robust Model-Checking of Linear-Time Properties in Timed Automata. | Patricia Bouyer, Nicolas Markey, Pierre-Alain Reynier |
| 2006 | Pattern Matching Statistics on Correlated Sources. | Jrmie Bourdon, Brigitte Valle |
| 2006 | On Behalf of the Seller and Society: Bicriteria Mechanisms for Unit-Demand Auctions. | Claudson F. Bornstein, Eduardo Sany Laber, Marcelo Mas |
| 2006 | Eliminating Cycles in the Discrete Torus. | Bla Bollobs, Guy Kindler, Imre Leader, Ryan O'Donnell |
| 2006 | Random Bichromatic Matchings. | Nayantara Bhatnagar, Dana Randall, Vijay V. Vazirani, Eric Vigoda |
| 2006 | An Algorithm for a Generalized Maximum Subsequence Problem. | Thorsten Bernholt, Thomas Hofmeister |
| 2006 | An Optimal Algorithm for the Continuous/Discrete Weighted 2-Center Problem in Trees. | Boaz Ben-Moshe, Binay K. Bhattacharya, Qiaosheng Shi |
| 2006 | Classical Computability and Fuzzy Turing Machines. | Benjamn Ren Callejas Bedregal, Santiago Figueira |
| 2006 | Optimally Adaptive Integration of Univariate Lipschitz Functions. | Ilya Baran, Erik D. Demaine, Dmitriy A. Katz |
| 2006 | Algorithmic Challenges in Web Search Engines. | Ricardo A. Baeza-Yates |
| 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 | Efficient Approximate Dictionary Look-Up for Long Words over Small Alphabets. | Abdullah N. Arslan |
| 2006 | Counting Proportions of Sets: Expressive Power with Almost Order. | Argimiro Arratia, Carlos E. Ortiz |
| 2006 | The Complexity of Diffuse Reflections in a Simple Polygon. | Boris Aronov, Alan R. Davis, John Iacono, Albert Siu Cheong Yu |
| 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 | Scoring Matrices That Induce Metrics on Sequences. | Eli Arajo, Jos Soares |
| 2006 | An Architecture for Provably Secure Computation. | Mikls Ajtai, Cynthia Dwork, Larry J. Stockmeyer |
| 2006 | On Clusters in Markov Chains. | Nir Ailon, Steve Chien, Cynthia Dwork |
| 2006 | A New GCD Algorithm for Quadratic Number Rings with Unique Factorization. | Saurabh Agarwal, Gudmund Skovbjerg Frandsen |