| 2003 | Classical deterministic complexity of Edmonds' Problem and quantum entanglement. | Leonid Gurvits |
| 2003 | Linear time encodable and list decodable codes. | Venkatesan Guruswami, Piotr Indyk |
| 2003 | Simpler and better approximation algorithms for network design. | Anupam Gupta, Amit Kumar, Tim Roughgarden |
| 2003 | On the fractal behavior of TCP. | Anna C. Gilbert, Howard J. Karloff |
| 2003 | Work-competitive scheduling for cooperative computing with dynamic groups. | Chryssis Georgiou, Alexander Russell, Alexander A. Shvartsman |
| 2003 | Lower bounds on the efficiency of encryption and digital signature schemes. | Rosario Gennaro, Yael Gertner, Jonathan Katz |
| 2003 | Well-separated pair decomposition for the unit-disk graph metric and its applications. | Jie Gao, Li Zhang |
| 2003 | Lower bounds on the amount of randomness in private computation. | Anna Gl, Adi Rosn |
| 2003 | A proof of Alon's second eigenvalue conjecture. | Joel Friedman |
| 2003 | Hidden translation and orbit coset in quantum computing. | Katalin Friedl, Gbor Ivanyos, Frdric Magniez, Miklos Santha, Pranab Sen |
| 2003 | A tight time lower bound for space-optimal implementations of multi-writer snapshots. | Panagiota Fatourou, Faith E. Fich, Eric Ruppert |
| 2003 | A tight bound on approximating arbitrary metrics by tree metrics. | Jittat Fakcharoenphol, Satish Rao, Kunal Talwar |
| 2003 | Approximate counting by dynamic programming. | Martin E. Dyer |
| 2003 | Touring a sequence of polygons. | Moshe Dror, Alon Efrat, Anna Lubiw, Joseph S. B. Mitchell |
| 2003 | A new multilayered PCP and the hardness of hypergraph vertex cover. | Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev |
| 2003 | Almost random graphs with simple hash functions. | Martin Dietzfelbinger, Philipp Woelfel |
| 2003 | Alpha-shapes and flow shapes are homotopy equivalent. | Tamal K. Dey, Joachim Giesen, Matthias John |
| 2003 | A new approach to dynamic all pairs shortest paths. | Camil Demetrescu, Giuseppe F. Italiano |
| 2003 | Non-interactive and reusable non-malleable commitment schemes. | Ivan Damgrd, Jens Groth |
| 2003 | Reconstructing curves in three (and higher) dimensional space from noisy data. | Don Coppersmith, Madhu Sudan |
| 2003 | A fast algorithm for computing steiner edge connectivity. | Richard Cole, Ramesh Hariharan |
| 2003 | Pricing network edges for heterogeneous selfish users. | Richard Cole, Yevgeniy Dodis, Tim Roughgarden |
| 2003 | Exponential algorithmic speedup by a quantum walk. | Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman |
| 2003 | Meet and merge: approximation algorithms for confluent flows. | Jiangzhuo Chen, Rajmohan Rajaraman, Ravi Sundaram |
| 2003 | Sublinear geometric algorithms. | Bernard Chazelle, Ding Liu, Avner Magen |