| 2003 | The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions. | Robert D. Kleinberg, Frank Thomson Leighton |
| 2003 | Hardness of Approximating the Shortest Vector Problem in High L | Subhash Khot |
| 2003 | Gossip-Based Computation of Aggregate Information. | David Kempe, Alin Dobra, Johannes Gehrke |
| 2003 | Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs. | Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko |
| 2003 | Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. | Jesse Kamp, David Zuckerman |
| 2003 | A Lower Bound for the Bounded Round Quantum Communication Complexity of Set Disjointness. | Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen |
| 2003 | Tight Lower Bounds for the Distinct Elements Problem. | Piotr Indyk, David P. Woodruff |
| 2003 | Logics for Reasoning about Cryptographic Constructions. | Russell Impagliazzo, Bruce M. Kapron |
| 2003 | Breaking a Time-and-Space Barrier in Constructing Full-Text Indices. | Wing-Kai Hon, Kunihiko Sadakane, Wing-Kin Sung |
| 2003 | A Non-Markovian Coupling for Randomly Sampling Colorings. | Thomas P. Hayes, Eric Vigoda |
| 2003 | Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem. | Anupam Gupta, Amit Kumar, Martin Pl, Tim Roughgarden |
| 2003 | Bounded Geometries, Fractals, and Low-Distortion Embeddings. | Anupam Gupta, Robert Krauthgamer, James R. Lee |
| 2003 | The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side. | Martin Grohe |
| 2003 | On the (In)security of the Fiat-Shamir Paradigm. | Shafi Goldwasser, Yael Tauman Kalai |
| 2003 | On the Implementation of Huge Random Objects. | Oded Goldreich, Shafi Goldwasser, Asaf Nussboim |
| 2003 | An In-Place Sorting with O(n log n) Comparisons and O(n) Moves. | Gianni Franceschini, Viliam Geffert |
| 2003 | Broadcasting Algorithms in Radio Networks with Unknown Topology. | Artur Czumaj, Wojciech Rytter |
| 2003 | A Polynomial Algorithm for Recognizing Perfect Graphs. | Grard Cornujols, Xinming Liu, Kristina Vuskovic |
| 2003 | A Group-Theoretic Approach to Fast Matrix Multiplication. | Henry Cohn, Christopher Umans |
| 2003 | Paths, Trees, and Minimum Latency Tours. | Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, Kunal Talwar |
| 2003 | Clustering with Qualitative Information. | Moses Charikar, Venkatesan Guruswami, Anthony Wirth |
| 2003 | On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences. | Timothy M. Chan |
| 2003 | Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua. | Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi |
| 2003 | Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem. | Andrei A. Bulatov, Vctor Dalmau |
| 2003 | Learning DNF from Random Walks. | Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio |