| 2003 | The computational complexity of some julia sets. | Robert Rettinger, Klaus Weihrauch |
| 2003 | New lattice based cryptographic constructions. | Oded Regev |
| 2003 | On average distortion of embedding metrics into the line and into L1. | Yuri Rabinovich |
| 2003 | Approximation algorithms for hierarchical location problems. | C. Greg Plaxton |
| 2003 | Uniform hashing in constant time and linear space. | Anna stlin, Rasmus Pagh |
| 2003 | New degree bounds for polynomial threshold functions. | Ryan O'Donnell, Rocco A. Servedio |
| 2003 | Learning juntas. | Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio |
| 2003 | Evolving sets and mixin. | Ben Morris, Yuval Peres |
| 2003 | Extractors: optimal up to constant factors. | Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, Avi Wigderson |
| 2003 | Bounded-concurrent secure two-party computation without setup assumptions. | Yehuda Lindell |
| 2003 | The intrinsic dimensionality of graphs. | Robert Krauthgamer, James R. Lee |
| 2003 | Short path queries in planar graphs in constant time. | Lukasz Kowalik, Maciej Kurowski |
| 2003 | Primal-dual meets local search: approximating MST's with nonuniform degree bounds. | Jochen Knemann, R. Ravi |
| 2003 | Consistent load balancing via spread minimization. | Robert D. Kleinberg, Frank Thomson Leighton |
| 2003 | Quantum time-space tradeoffs for sorting. | Hartmut Klauck |
| 2003 | Generating random regular graphs. | Jeong Han Kim, Van H. Vu |
| 2003 | Exponential lower bound for 2-query locally decodable codes via a quantum argument. | Iordanis Kerenidis, Ronald de Wolf |
| 2003 | Dynamic rectangular intersection with priorities. | Haim Kaplan, Eyal Molad, Robert Endre Tarjan |
| 2003 | Boosting in the presence of noise. | Adam Kalai, Rocco A. Servedio |
| 2003 | Derandomizing polynomial identity tests means proving circuit lower bounds. | Valentine Kabanets, Russell Impagliazzo |
| 2003 | Two applications of information complexity. | T. S. Jayram, Ravi Kumar, D. Sivakumar |
| 2003 | Cell-probe lower bounds for the partial match problem. | T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani |
| 2003 | On the sample size of k-restricted min-wise independent permutations and other k-wise distributions. | Toshiya Itoh, Yoshinori Takei, Jun Tarui |
| 2003 | Randomly coloring graphs of girth at least five. | Thomas P. Hayes |
| 2003 | Polylogarithmic inapproximability. | Eran Halperin, Robert Krauthgamer |