| 2003 | A fast algorithm for computing steiner edge connectivity. Richard Cole, Ramesh Hariharan |
| 2003 | A new approach to dynamic all pairs shortest paths. Camil Demetrescu, Giuseppe F. Italiano |
| 2003 | A new multilayered PCP and the hardness of hypergraph vertex cover. Irit Dinur, Venkatesan Guruswami, Subhash Khot, Oded Regev |
| 2003 | A proof of Alon's second eigenvalue conjecture. Joel Friedman |
| 2003 | A stochastic process on the hypercube with applications to peer-to-peer networks. Micah Adler, Eran Halperin, Richard M. Karp, Vijay V. Vazirani |
| 2003 | A sublinear algorithm for weakly approximating edit distance. Tugkan Batu, Funda Ergün, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami |
| 2003 | A tight bound on approximating arbitrary metrics by tree metrics. Jittat Fakcharoenphol, Satish Rao, Kunal Talwar |
| 2003 | A tight time lower bound for space-optimal implementations of multi-writer snapshots. Panagiota Fatourou, Faith E. Fich, Eric Ruppert |
| 2003 | Adiabatic quantum state generation and statistical zero knowledge. Dorit Aharonov, Amnon Ta-Shma |
| 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 | Approximate counting by dynamic programming. Martin E. Dyer |
| 2003 | Approximation algorithms for hierarchical location problems. C. Greg Plaxton |
| 2003 | Approximation schemes for clustering problems. Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani |
| 2003 | Better streaming algorithms for clustering problems. Moses Charikar, Liadan O'Callaghan, Rina Panigrahy |
| 2003 | Boosting in the presence of noise. Adam Kalai, Rocco A. Servedio |
| 2003 | Bounded-concurrent secure two-party computation without setup assumptions. Yehuda Lindell |
| 2003 | Cell-probe lower bounds for the partial match problem. T. S. Jayram, Subhash Khot, Ravi Kumar, Yuval Rabani |
| 2003 | Classical deterministic complexity of Edmonds' Problem and quantum entanglement. Leonid Gurvits |
| 2003 | Consistent load balancing via spread minimization. Robert D. Kleinberg, Frank Thomson Leighton |
| 2003 | Constant factor approximation of vertex-cuts in planar graphs. Eyal Amir, Robert Krauthgamer, Satish Rao |
| 2003 | Cutting triangular cycles of lines in space. Boris Aronov, Vladlen Koltun, Micha Sharir |
| 2003 | Derandomizing polynomial identity tests means proving circuit lower bounds. Valentine Kabanets, Russell Impagliazzo |
| 2003 | Distinct distances in three and higher dimensions. Boris Aronov, János Pach, Micha Sharir, Gábor Tardos |
| 2003 | Dynamic rectangular intersection with priorities. Haim Kaplan, Eyal Molad, Robert Endre Tarjan |
| 2003 | Evolving sets and mixin. Ben Morris, Yuval Peres |
| 2003 | Exponential algorithmic speedup by a quantum walk. Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, Daniel A. Spielman |
| 2003 | Exponential lower bound for 2-query locally decodable codes via a quantum argument. Iordanis Kerenidis, Ronald de Wolf |
| 2003 | Extractors: optimal up to constant factors. Chi-Jen Lu, Omer Reingold, Salil P. Vadhan, Avi Wigderson |
| 2003 | Generating random regular graphs. Jeong Han Kim, Van H. Vu |
| 2003 | Hidden translation and orbit coset in quantum computing. Katalin Friedl, Gábor Ivanyos, Frédéric Magniez, Miklos Santha, Pranab Sen |
| 2003 | Integer priority queues with decrease key in constant time and the single source shortest paths problem. Mikkel Thorup |
| 2003 | Learning juntas. Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio |
| 2003 | Linear time encodable and list decodable codes. Venkatesan Guruswami, Piotr Indyk |
| 2003 | Lower bounds on the amount of randomness in private computation. Anna Gál, Adi Rosén |
| 2003 | Lower bounds on the efficiency of encryption and digital signature schemes. Rosario Gennaro, Yael Gertner, Jonathan Katz |
| 2003 | Management of multi-queue switches in QoS networks. Yossi Azar, Yossi Richter |
| 2003 | Meet and merge: approximation algorithms for confluent flows. Jiangzhuo Chen, Rajmohan Rajaraman, Ravi Sundaram |
| 2003 | Modified log-sobolev inequalities, mixing and hypercontractivity. Sergey G. Bobkov, Prasad Tetali |
| 2003 | Near-optimal network design with selfish agents. Elliot Anshelevich, Anirban Dasgupta, Éva Tardos, Tom Wexler |
| 2003 | New degree bounds for polynomial threshold functions. Ryan O'Donnell, Rocco A. Servedio |
| 2003 | New lattice based cryptographic constructions. Oded Regev |
| 2003 | Non-interactive and reusable non-malleable commitment schemes. Ivan Damgård, Jens Groth |
| 2003 | OPT versus LOAD in dynamic storage allocation. Adam L. Buchsbaum, Howard J. Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup |
| 2003 | On average distortion of embedding metrics into the line and into L1. Yuri Rabinovich |
| 2003 | On metric ramsey-type phenomena. Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor |
| 2003 | On the fractal behavior of TCP. Anna C. Gilbert, Howard J. Karloff |
| 2003 | On the limits of cache-obliviousness. Gerth Stølting Brodal, Rolf Fagerberg |
| 2003 | On the power of quantum fingerprinting. Andrew Chi-Chih Yao |
| 2003 | On the sample size of k-restricted min-wise independent permutations and other k-wise distributions. Toshiya Itoh, Yoshinori Takei, Jun Tarui |
| 2003 | Optimal oblivious routing in polynomial time. Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Räcke |
| 2003 | Optimal probabilistic fingerprint codes. Gábor Tardos |
| 2003 | Polylogarithmic inapproximability. Eran Halperin, Robert Krauthgamer |
| 2003 | Pricing network edges for heterogeneous selfish users. Richard Cole, Yevgeniy Dodis, Tim Roughgarden |
| 2003 | Primal-dual meets local search: approximating MST's with nonuniform degree bounds. Jochen Könemann, R. Ravi |
| 2003 | Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA Lawrence L. Larmore, Michel X. Goemans |
| 2003 | Quantum time-space tradeoffs for sorting. Hartmut Klauck |
| 2003 | Random knapsack in expected polynomial time. René Beier, Berthold Vöcking |
| 2003 | Randomly coloring graphs of girth at least five. Thomas P. Hayes |
| 2003 | Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson |
| 2003 | Reconstructing curves in three (and higher) dimensional space from noisy data. Don Coppersmith, Madhu Sudan |
| 2003 | Reducing truth-telling online mechanisms to online optimization. Baruch Awerbuch, Yossi Azar, Adam Meyerson |
| 2003 | Sampling lower bounds via information theory. Ziv Bar-Yossef |
| 2003 | Server scheduling in the L Nikhil Bansal, Kirk Pruhs |
| 2003 | Short path queries in planar graphs in constant time. Lukasz Kowalik, Maciej Kurowski |
| 2003 | Simpler and better approximation algorithms for network design. Anupam Gupta, Amit Kumar, Tim Roughgarden |
| 2003 | Some 3CNF properties are hard to test. Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova |
| 2003 | Space efficient dynamic stabbing with fast queries. Mikkel Thorup |
| 2003 | Sublinear geometric algorithms. Bernard Chazelle, Ding Liu, Avner Magen |
| 2003 | Testing subgraphs in directed graphs. Noga Alon, Asaf Shapira |
| 2003 | The computational complexity of some julia sets. Robert Rettinger, Klaus Weihrauch |
| 2003 | The intrinsic dimensionality of graphs. Robert Krauthgamer, James R. Lee |
| 2003 | The online set cover problem. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor |
| 2003 | The threshold for random k-SAT is 2 Dimitris Achlioptas, Yuval Peres |
| 2003 | The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice. Miklós Ajtai |
| 2003 | Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions. Martin Sauerhoff, Philipp Woelfel |
| 2003 | Touring a sequence of polygons. Moshe Dror, Alon Efrat, Anna Lubiw, Joseph S. B. Mitchell |
| 2003 | Two applications of information complexity. T. S. Jayram, Ravi Kumar, D. Sivakumar |
| 2003 | Uniform hashing in constant time and linear space. Anna Östlin, Rasmus Pagh |
| 2003 | Well-separated pair decomposition for the unit-disk graph metric and its applications. Jie Gao, Li Zhang |
| 2003 | Work-competitive scheduling for cooperative computing with dynamic groups. Chryssis Georgiou, Alexander Russell, Alexander A. Shvartsman |