| 2005 | The influence of search engines on preferential attachment. | Soumen Chakrabarti, Alan M. Frieze, Juan Vera |
| 2005 | An O(VE) algorithm for ear decompositions of matching-covered graphs. | Marcelo Henriques de Carvalho, Joseph Cheriyan |
| 2005 | Improved range-summable random variable construction algorithms. | A. Robert Calderbank, Anna C. Gilbert, Kirill Levchenko, S. Muthukrishnan, Martin Strauss |
| 2005 | Multidimensional balanced allocations. | Andrei Z. Broder, Michael Mitzenmacher |
| 2005 | The relative worst order ratio applied to paging. | Joan Boyar, Lene M. Favrholdt, Kim S. Larsen |
| 2005 | Near-optimal online auctions. | Avrim Blum, Jason D. Hartline |
| 2005 | Dictionaries using variable-length keys and data, with applications. | Daniel K. Blandford, Guy E. Blelloch |
| 2005 | On the spread of viruses on the internet. | Noam Berger, Christian Borgs, Jennifer T. Chayes, Amin Saberi |
| 2005 | A constant-factor approximation algorithm for optimal terrain guarding. | Boaz Ben-Moshe, Matthew J. Katz, Joseph S. B. Mitchell |
| 2005 | Sharing the cost more efficiently: improved approximation for multicommodity rent-or-buy. | Luca Becchetti, Jochen Knemann, Stefano Leonardi, Martin Pl |
| 2005 | New constructions of (alpha, beta)-spanners and purely additive spanners. | Surender Baswana, Telikepalli Kavitha, Kurt Mehlhorn, Seth Pettie |
| 2005 | Job shop scheduling with unit processing times. | Nikhil Bansal, Tracy Kimbrel, Maxim Sviridenko |
| 2005 | Approximating the average response time in broadcast scheduling. | Nikhil Bansal, Moses Charikar, Sanjeev Khanna, Joseph Naor |
| 2005 | Loop quantum gravity. | John C. Baez |
| 2005 | Approximation algorithms for low-distortion embeddings into low-dimensional spaces. | Mihai Badoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Rcke, R. Ravi, Anastasios Sidiropoulos |
| 2005 | Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group. | Lszl Babai, Thomas P. Hayes |
| 2005 | Improved recommendation systems. | Baruch Awerbuch, Boaz Patt-Shamir, David Peleg, Mark R. Tuttle |
| 2005 | Online client-server load balancing without global information. | Baruch Awerbuch, Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, Tom Leighton |
| 2005 | Dotted interval graphs and high throughput genotyping. | Yonatan Aumann, Moshe Lewenstein, Oren Melamud, Ron Y. Pinter, Zohar Yakhini |
| 2005 | Inoculation strategies for victims of viruses and the sum-of-squares partition problem. | James Aspnes, Kevin L. Chang, Aleksandr Yampolskiy |
| 2005 | Space-time tradeoffs for approximate spherical range counting. | Sunil Arya, Theocharis Malamatos, David M. Mount |
| 2005 | On geometric permutations induced by lines transversal through a fixed point. | Boris Aronov, Shakhar Smorodinsky |
| 2005 | On approximating the depth and related problems. | Boris Aronov, Sariel Har-Peled |
| 2005 | Coins make quantum walks faster. | Andris Ambainis, Julia Kempe, Alexander Rivosh |
| 2005 | Linear equations, arithmetic progressions and hypergraph property testing. | Noga Alon, Asaf Shapira |