| 2003 | A spectral technique for random satisfiable 3CNF formulas. | Abraham Flaxman |
| 2003 | The set-associative cache performance of search trees. | James D. Fix |
| 2003 | An improved approximation algorithm for the 0-extension problem. | Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar |
| 2003 | The k-traveling repairman problem. | Jittat Fakcharoenphol, Chris Harrelson, Satish Rao |
| 2003 | Comparing top k lists. | Ronald Fagin, Ravi Kumar, D. Sivakumar |
| 2003 | Dynamic generators of topologically embedded graphs. | David Eppstein |
| 2003 | Sublogarithmic approximation for telephone multicast: path out of jungle. | Michael Elkin, Guy Kortsarz |
| 2003 | A combinatorial algorithm for computing a maximum independent set in a t-perfect graph. | Friedrich Eisenbrand, Stefan Funke, Naveen Garg, Jochen Knemann |
| 2003 | An approximation algorithm for cutting out convex polygons. | Adrian Dumitrescu |
| 2003 | Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons. | Devdatt P. Dubhashi, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan, Aravind Srinivasan |
| 2003 | Pass efficient algorithms for approximating large matrices. | Petros Drineas, Ravi Kannan |
| 2003 | Non-independent randomized rounding. | Benjamin Doerr |
| 2003 | Who cares about permanents? | Persi Diaconis |
| 2003 | Certifying and repairing solutions to large LPs how good are LP-solvers? | Marcel Dhiflaoui, Stefan Funke, Carsten Kwappik, Kurt Mehlhorn, Michael Seel, Elmar Schmer, Ralph Schulte, Dennis Weber |
| 2003 | Perturbations and vertex removal in a 3D delaunay triangulation. | Olivier Devillers, Monique Teillaud |
| 2003 | Quantum algorithms for some hidden shift problems. | Wim van Dam, Sean Hallgren, Lawrence Ip |
| 2003 | Sublinear-time approximation of Euclidean minimum spanning tree. | Artur Czumaj, Funda Ergn, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, Christian Sohler |
| 2003 | Chain decompositions and independent trees in 4-connected graphs. | Sean Curran, Orlando Lee, Xingxing Yu |
| 2003 | Random walks on the vertices of transportation polytopes with constant number of sources. | Mary Cryan, Martin E. Dyer, Haiko Mller, Leen Stougie |
| 2003 | Random MAX SAT, random MAX CUT, and their phase transitions. | Don Coppersmith, David Gamarnik, Mohammad Taghi Hajiaghayi, Gregory B. Sorkin |
| 2003 | The cover time of sparse random graphs. | Colin Cooper, Alan M. Frieze |
| 2003 | Multidimensional matching and fast search in suffix trees. | Richard Cole, Moshe Lewenstein |
| 2003 | Efficient sequences of trials. | Edith Cohen, Amos Fiat, Haim Kaplan |
| 2003 | Graded conforming Delaunay tetrahedralization with bounded radius-edge ratio. | Siu-Wing Cheng, Sheung-Hung Poon |
| 2003 | Edge disjoint paths revisited. | Chandra Chekuri, Sanjeev Khanna |