| 2005 | Approximation Algorithms for Scheduling on Multiple Machines. | V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan |
| 2005 | Query Incentive Networks. | Jon M. Kleinberg, Prabhakar Raghavan |
| 2005 | An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs. | Jon M. Kleinberg |
| 2005 | A linear-time approximation scheme for planar weighted TSP. | Philip N. Klein |
| 2005 | The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l | Subhash Khot, Nisheeth K. Vishnoi |
| 2005 | Nonembeddability theorems via Fourier analysis. | Subhash Khot, Assaf Naor |
| 2005 | On the Unique Games Conjecture. | Subhash Khot |
| 2005 | Almost Orthogonal Linear Codes are Locally Testable. | Tali Kaufman, Simon Litsyn |
| 2005 | Beyond VCG: Frugality of Truthful Mechanisms. | Anna R. Karlin, David Kempe, Tami Tamir |
| 2005 | Agnostically Learning Halfspaces. | Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio |
| 2005 | Rational Secure Computation and Ideal Mechanism Design. | Sergei Izmalkov, Silvio Micali, Matt Lepinski |
| 2005 | A general lower bound for mixing of single-site dynamics on graphs. | Thomas P. Hayes, Alistair Sinclair |
| 2005 | An Algorithmic Version of the Hypergraph Regularity Method. | Penny E. Haxell, Brendan Nagle, Vojtech Rdl |
| 2005 | Lower Bounds for the Noisy Broadcast Problem. | Navin Goyal, Guy Kindler, Michael E. Saks |
| 2005 | On the Impossibility of Obfuscation with Auxiliary Input. | Shafi Goldwasser, Yael Tauman Kalai |
| 2005 | Sink Equilibria and Convergence. | Michel X. Goemans, Vahab S. Mirrokni, Adrian Vetta |
| 2005 | Deterministic Extractors for Affine Sources over Large Fields. | Ariel Gabizon, Ran Raz |
| 2005 | Linear Lower Bounds on Real-World Implementations of Concurrent Objects. | Faith Ellen Fich, Danny Hendler, Nir Shavit |
| 2005 | Structuring labeled trees for optimal succinctness, and beyond. | Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini, S. Muthukrishnan |
| 2005 | How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems. | Kedar Dhamdhere, Vineet Goyal, R. Ravi, Mohit Singh |
| 2005 | Improved Smoothed Analysis of the Shadow Vertex Simplex Method. | Amit Deshpande, Daniel A. Spielman |
| 2005 | Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring. | Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi |
| 2005 | On Learning Mixtures of Heavy-Tailed Distributions. | Anirban Dasgupta, John E. Hopcroft, Jon M. Kleinberg, Mark Sandler |
| 2005 | Cryptography In the Bounded Quantum-Storage Model. | Ivan Damgrd, Serge Fehr, Louis Salvail, Christian Schaffner |
| 2005 | Group-theoretic Algorithms for Matrix Multiplication. | Henry Cohn, Robert D. Kleinberg, Balzs Szegedy, Christopher Umans |