| 2003 | Embedding k-outerplanar graphs into l1. | Chandra Chekuri, Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair |
| 2003 | Algorithms for k-colouring and finding maximal independent sets. | Jesper Makholm Byskov |
| 2003 | Quantum property testing. | Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Rhrig |
| 2003 | Lower bounds for external memory dictionaries. | Gerth Stlting Brodal, Rolf Fagerberg |
| 2003 | Sparse distance preservers and additive spanners. | Bla Bollobs, Don Coppersmith, Michael Elkin |
| 2003 | Directed scale-free graphs. | Bla Bollobs, Christian Borgs, Jennifer T. Chayes, Oliver Riordan |
| 2003 | On the combinatorial complexity of euclidean Voronoi cells and convex hulls of d-dimensional spheres. | Jean-Daniel Boissonnat, Menelaos I. Karavelas |
| 2003 | Online learning in online auctions. | Avrim Blum, Vijay Kumar, Atri Rudra, Felix Wu |
| 2003 | Space-efficient finger search on degree-balanced search trees. | Guy E. Blelloch, Bruce M. Maggs, Shan Leung Maverick Woo |
| 2003 | A new approximation algorithm for the asymmetric TSP with triangle inequality. | Markus Blser |
| 2003 | Compact representations of separable graphs. | Daniel K. Blandford, Guy E. Blelloch, Ian A. Kash |
| 2003 | Computing homotopic shortest paths in the plane. | Sergei Bespamyatnikh |
| 2003 | Mbius-invariant natural neighbor interpolation. | Marshall W. Bern, David Eppstein |
| 2003 | Optimizing misdirection. | Piotr Berman, Piotr Krysta |
| 2003 | Maintaining all-pairs approximate shortest paths under deletion of edges. | Surender Baswana, Ramesh Hariharan, Sandeep Sen |
| 2003 | Multi-embedding and path approximation of metric spaces. | Yair Bartal, Manor Mendel |
| 2003 | Dynamic construction of Bluetooth scatternets of fixed degree and low diameter. | Lali Barrire, Pierre Fraigniaud, Lata Narayanan, Jaroslav Opatrny |
| 2003 | Straight-skeleton based contour interpolation. | Gill Barequet, Michael T. Goodrich, Aya Levi-Steiner, Dvir Steiner |
| 2003 | Scheduling techniques for media-on-demand. | Amotz Bar-Noy, Richard E. Ladner, Tami Tamir |
| 2003 | Minimizing weighted flow time. | Nikhil Bansal, Kedar Dhamdhere |
| 2003 | Smaller core-sets for balls. | Mihai Badoiu, Kenneth L. Clarkson |
| 2003 | Approximation algorithm for embedding metrics into a two-dimensional space. | Mihai Badoiu |
| 2003 | Skip graphs. | James Aspnes, Gauri Shah |
| 2003 | Faster approximation algorithms for the minimum latency problem. | Aaron Archer, David P. Williamson |
| 2003 | An approximate truthful mechanism for combinatorial auctions with single parameter agents. | Aaron Archer, Christos H. Papadimitriou, Kunal Talwar, va Tardos |