| 2003 | Quantum Circuits with Unbounded Fan-out. | Peter Hyer, Robert Spalek |
| 2003 | Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids. | Petr Hlinen |
| 2003 | On the Difficulty of Some Shortest Path Problems. | John Hershberger, Subhash Suri, Amit M. Bhosle |
| 2003 | On the Confluence of Linear Shallow Term Rewrite Systems. | Guillem Godoy, Ashish Tiwari, Rakesh M. Verma |
| 2003 | Evolutionary Algorithms and the Maximum Matching Problem. | Oliver Giel, Ingo Wegener |
| 2003 | Algebraic Characterizations of Small Classes of Boolean Functions. | Ricard Gavald, Denis Thrien |
| 2003 | Space Efficient Hash Tables with Worst Case Constant Access Time. | Dimitris Fotakis, Rasmus Pagh, Peter Sanders, Paul G. Spirakis |
| 2003 | Computing Shortest Paths with Uncertainty. | Toms Feder, Rajeev Motwani, Liadan O'Callaghan, Chris Olston, Rina Panigrahy |
| 2003 | Representing Graph Metrics with Fewest Edges. | Toms Feder, Adam Meyerson, Rajeev Motwani, Liadan O'Callaghan, Rina Panigrahy |
| 2003 | On Shortest-Path All-Optical Networks without Wavelength Conversion Requirements. | Thomas Erlebach, Stamatis Stefanakos |
| 2003 | Adaptive Sorting and the Information Theoretic Lower Bound. | Amr Elmasry, Michael L. Fredman |
| 2003 | The Inference Problem for Propositional Circumscription of Affine Formulas Is coNP-Complete. | Arnaud Durand, Miki Hermann |
| 2003 | Distributed Soft Path Coloring. | Peter Damaschke |
| 2003 | Colouring Random Graphs in Expected Polynomial Time. | Amin Coja-Oghlan, Anusch Taraz |
| 2003 | Finding Large Independent Sets in Polynomial Expected Time. | Amin Coja-Oghlan |
| 2003 | Analysis of the Harmonic Algorithm for Three Servers. | Marek Chrobak, Jir Sgall |
| 2003 | On the Ultimate Complexity of Factorials. | Qi Cheng |
| 2003 | On Sand Automata. | Julien Cervelle, Enrico Formenti |
| 2003 | Competing Provers Yield Improved Karp-Lipton Collapse Results. | Jin-yi Cai, Venkatesan T. Chakaravarthy, Lane A. Hemaspaandra, Mitsunori Ogihara |
| 2003 | Some Results on Derandomization. | Harry Buhrman, Lance Fortnow, Aduri Pavan |
| 2003 | One Bit of Advice. | Harry Buhrman, Richard Chang, Lance Fortnow |
| 2003 | Durations, Parametric Model-Checking in Timed Automata with Presburger Arithmetic. | Vronique Bruyre, Emmanuel Dall'Olio, Jean-Franois Raskin |
| 2003 | Randomized Jumplists: A Jump-and-Walk Dictionary Data Structure. | Herv Brnnimann, Frdric Cazals, Marianne Durand |
| 2003 | The Inversion Problem for Computable Linear Operators. | Vasco Brattka |
| 2003 | Untameable Timed Automata! | Patricia Bouyer |