| 2005 | Coresets in dynamic geometric data streams. | Gereon Frahling, Christian Sohler |
| 2005 | Hierarchies for semantic classes. | Lance Fortnow, Rahul Santhanam, Luca Trevisan |
| 2005 | Beyond NP: the work and legacy of Larry Stockmeyer. | Lance Fortnow |
| 2005 | On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem. | Abraham Flaxman, Alan M. Frieze, Juan Carlos Vera |
| 2005 | Testing versus estimation of graph properties. | Eldar Fischer, Ilan Newman |
| 2005 | Improved approximation algorithms for minimum-weight vertex separators. | Uriel Feige, Mohammad Taghi Hajiaghayi, James R. Lee |
| 2005 | Lower-stretch spanning trees. | Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng |
| 2005 | Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. | Zeev Dvir, Amir Shpilka |
| 2005 | Correcting errors without leaking partial information. | Yevgeniy Dodis, Adam D. Smith |
| 2005 | Approximation algorithms for combinatorial auctions with complement-free bidders. | Shahar Dobzinski, Noam Nisan, Michael Schapira |
| 2005 | Approximately counting integral flows and cell-bounded contingency tables. | Mary Cryan, Martin E. Dyer, Dana Randall |
| 2005 | Market equilibrium via the excess demand function. | Bruno Codenotti, Benton McCune, Kasturi R. Varadarajan |
| 2005 | A new strategy for querying priced information. | Ferdinando Cicalese, Eduardo Sany Laber |
| 2005 | The price of anarchy of finite congestion games. | George Christodoulou, Elias Koutsoupias |
| 2005 | Cooperative asynchronous update of shared memory. | Bogdan S. Chlebus, Dariusz R. Kowalski |
| 2005 | Approximation algorithms for network design with metric costs. | Joseph Cheriyan, Adrian Vetta |
| 2005 | On algorithms for discrete and approximate brouwer fixed points. | Xi Chen, Xiaotie Deng |
| 2005 | Multicommodity flow, well-linked terminals, and routing problems. | Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd |
| 2005 | On non-uniform multicommodity buy-at-bulk network design. | Moses Charikar, Adriana Karagiozova |
| 2005 | Approximation techniques for utilitarian mechanism design. | Patrick Briest, Piotr Krysta, Berthold Vcking |
| 2005 | Tree-walking automata do not recognize all regular languages. | Mikolaj Bojanczyk, Thomas Colcombet |
| 2005 | Pseudorandom generators for low degree polynomials. | Andrej Bogdanov |
| 2005 | Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read. | Itai Benjamini, Oded Schramm, David Bruce Wilson |
| 2005 | Simple PCPs with poly-log rate and query complexity. | Eli Ben-Sasson, Madhu Sudan |
| 2005 | Fast quantum byzantine agreement. | Michael Ben-Or, Avinatan Hassidim |