| 2003 | Complete Classifications for the Communication Complexity of Regular Languages. | Pascal Tesson, Denis Thrien |
| 2003 | The Price of Truth: Frugality in Truthful Mechanisms. | Kunal Talwar |
| 2003 | The Complexity of Resolution with Generalized Symmetry Rules. | Stefan Szeider |
| 2003 | Rectangle Visibility Graphs: Characterization, Construction, and Compaction. | Ileana Streinu, Sue Whitesides |
| 2003 | Wadge Degrees of omega-Languages of Deterministic Turing Machines. | Victor L. Selivanov |
| 2003 | Lattice Reduction by Random Sampling and Birthday Methods. | Claus-Peter Schnorr |
| 2003 | Strong Reductions and Immunity for Exponential Time. | Marcus Schaefer, Frank Stephan |
| 2003 | Randomness versus Nondeterminism for Read-Once and Read- k Branching Programs. | Martin Sauerhoff |
| 2003 | Alternative Algorithms for Counting All Matchings in Graphs. | Piotr Sankowski |
| 2003 | The Intrinsic Universality Problem of One-Dimensional Cellular Automata. | Nicolas Ollinger |
| 2003 | On the Complexity of Finding a Local Maximum of Functions on Discrete Planar Subsets. | Anton Mityagin |
| 2003 | Performance Ratios for the Differencing Method Applied to the Balanced Number Partitioning Problem. | Wil Michiels, Jan H. M. Korst, Emile H. L. Aarts, Jan van Leeuwen |
| 2003 | The Complexity of Membership Problems for Circuits over Sets of Natural Numbers. | Pierre McKenzie, Klaus W. Wagner |
| 2003 | Algorithms for Transposition Invariant String Matching. | Veli Mkinen, Gonzalo Navarro, Esko Ukkonen |
| 2003 | Cake-Cutting Is Not a Piece of Cake. | Malik Magdon-Ismail, Costas Busch, Mukkai S. Krishnamoorthy |
| 2003 | Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer. | Ching-Chi Lin, Hsueh-I Lu, I-Fan Sun |
| 2003 | Optimization in Arrangements. | Stefan Langerman, William L. Steiger |
| 2003 | Decidable Theories of Cayley-Graphs. | Dietrich Kuske, Markus Lohrey |
| 2003 | Solving Order Constraints in Logarithmic Space. | Andrei A. Krokhin, Benot Larose |
| 2003 | Faster Deterministic Broadcasting in Ad Hoc Radio Networks. | Dariusz R. Kowalski, Andrzej Pelc |
| 2003 | On the Representation of Boolean Predicates of the Diffie-Hellman Function. | Eike Kiltz |
| 2003 | The Commutation with Codes and Ternary Sets of Words. | Juhani Karhumki, Michel Latteux, Ion Petre |
| 2003 | Private Computations in Networks: Topology versus Randomness. | Andreas Jakoby, Maciej Liskiewicz, Rdiger Reischuk |
| 2003 | Strong Stability in the Hospitals/Residents Problem. | Robert W. Irving, David F. Manlove, Sandy Scott |
| 2003 | Fast Algorithms for Extended Regular Expression Matching and Searching. | Lucian Ilie, Baozhen Shan, Sheng Yu |