| 2006 | Untitled record | Moses Charikar, Mohammad Taghi Hajiaghayi, Howard J. Karloff, Satish Rao |
| 2006 | Extra unit-speed machines are almost as powerful as speedy machines for competitive flow time scheduling. | Ho-Leung Chan, Tak Wah Lam, Kin-Shing Liu |
| 2006 | The space complexity of pass-efficient algorithms for clustering. | Kevin L. Chang, Ravi Kannan |
| 2006 | Small hop-diameter sparse spanners for doubling metrics. | T.-H. Hubert Chan, Anupam Gupta |
| 2006 | A dynamic data structure for 3-d convex hulls and 2-d nearest neighbor queries. | Timothy M. Chan |
| 2006 | All-pairs shortest paths for unweighted undirected graphs in | Timothy M. Chan |
| 2006 | Many distances in planar graphs. | Sergio Cabello |
| 2006 | Relating singular values and discrepancy of weighted directed graphs. | Steven Butler |
| 2006 | Quantum verification of matrix products. | Harry Buhrman, Robert Spalek |
| 2006 | Cache-oblivious string dictionaries. | Gerth Stlting Brodal, Rolf Fagerberg |
| 2006 | Single-minded unlimited supply pricing on sparse instances. | Patrick Briest, Piotr Krysta |
| 2006 | Simultaneous diagonal flips in plane triangulations. | Prosenjit Bose, Jurek Czyzowicz, Zhicheng Gao, Pat Morin, David R. Wood |
| 2006 | An | Glencora Borradaile, Philip N. Klein |
| 2006 | Simpler algorithm for estimating frequency moments of data streams. | Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, Chandan Saha |
| 2006 | Accelerating simulated annealing for the permanent and combinatorial counting problems. | Ivona Bezkov, Daniel Stefankovic, Vijay V. Vazirani, Eric Vigoda |
| 2006 | Sampling binary contingency tables with a greedy start. | Ivona Bezkov, Nayantara Bhatnagar, Eric Vigoda |
| 2006 | 8/7-approximation algorithm for (1, 2)-TSP. | Piotr Berman, Marek Karpinski |
| 2006 | Vertical ray shooting and computing depth orders for fat objects. | Mark de Berg, Chris Gray |
| 2006 | Distributed selfish load balancing. | Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg, Paul W. Goldberg, Zengjian Hu, Russell A. Martin |
| 2006 | The Knuth-Yao quadrangle-inequality speedup is a consequence of total-monotonicity. | Wolfgang W. Bein, Mordecai J. Golin, Lawrence L. Larmore, Yan Zhang |
| 2006 | Oblivious string embeddings and edit distance approximations. | Tugkan Batu, Funda Ergn, Sleyman Cenk Sahinalp |
| 2006 | Scheduling unit tasks to minimize the number of idle periods: a polynomial time algorithm for offline dynamic power management. | Philippe Baptiste |
| 2006 | Improved approximation algorithms for broadcast scheduling. | Nikhil Bansal, Don Coppersmith, Maxim Sviridenko |
| 2006 | Counting without sampling: new algorithms for enumeration problems using statistical physics. | Antar Bandyopadhyay, David Gamarnik |
| 2006 | Single-value combinatorial auctions and implementation in undominated strategies. | Moshe Babaioff, Ron Lavi, Elan Pavlov |