| 2003 | Dimension- and Time-Hierarchies for Small Time Bounds. | Martin Kutrib |
| 2003 | On the Exponentiation of Languages. | Werner Kuich, Klaus W. Wagner |
| 2003 | Periodic Multisorting Comparator Networks. | Marcin Kik |
| 2003 | Circuits on Cylinders. | Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay |
| 2003 | Competitive Exploration of Rectilinear Polygons. | Mikael Hammar, Bengt J. Nilsson, Mia Persson |
| 2003 | Languages Defined by Generalized Equality Sets. | Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux |
| 2003 | Constructing Sparse t-Spanners with Small Separators. | Joachim Gudmundsson |
| 2003 | On Exact and Approximation Algorithms for Distinguishing Substring Selection. | Jens Gramm, Jiong Guo, Rolf Niedermeier |
| 2003 | Graph Searching, Elimination Trees, and a Generalization of Bandwidth. | Fedor V. Fomin, Pinar Heggernes, Jan Arne Telle |
| 2003 | Compositionality of Hennessy-Milner Logic through Structural Operational Semantics. | Wan J. Fokkink, Rob J. van Glabbeek, Paulien de Wind |
| 2003 | Complexity of Approximating Closest Substring Problems. | Patricia A. Evans, Andrew D. Smith |
| 2003 | An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates. | Ivan Damgrd, Gudmund Skovbjerg Frandsen |
| 2003 | Efficient Algorithms for GCD and Cubic Residuosity in the Ring of Eisenstein Integers. | Ivan Damgrd, Gudmund Skovbjerg Frandsen |
| 2003 | Fast Perfect Phylogeny Haplotype Inference. | Peter Damaschke |
| 2003 | Certifying Unsatisfiability of Random 2 | Amin Coja-Oghlan, Andreas Goerdt, Andr Lanka, Frank Schdlich |
| 2003 | Composing Equipotent Teams. | Mark Cieliebak, Stephan J. Eidenbenz, Aris Pagourtzis |
| 2003 | Inapproximability Results for Bounded Variants of Optimization Problems. | Miroslav Chlebk, Janka Chlebkov |
| 2003 | Context-Sensitive Equivalences for Non-interference Based Protocol Analysis. | Michele Bugliesi, Ambra Ceccato, Sabina Rossi |
| 2003 | Linear Time Algorithms for Some NP-Complete Problems on (P | Hans L. Bodlaender, Andreas Brandstdt, Dieter Kratsch, Michal Rao, Jeremy P. Spinrad |
| 2003 | Operations Preserving Recognizable Languages. | Jean Berstel, Luc Boasson, Olivier Carton, Bruno Petazzoni, Jean-Eric Pin |
| 2003 | An Improved Analysis of Goemans and Williamson's LP-Relaxation for MAX SAT. | Takao Asano |
| 2003 | One-Way Communication Complexity of Symmetric Boolean Functions. | Jan Arpe, Andreas Jakoby, Maciej Liskiewicz |
| 2003 | Proving Integrality Gaps without Knowing the Linear Program. | Sanjeev Arora |
| 2003 | Using Depth to Capture Average-Case Complexity. | Luis Antunes, Lance Fortnow, N. V. Vinodchandran |
| 2003 | Approximating the Pareto Curve with Local Search for the Bicriteria TSP (1, 2) Problem. | Eric Angel, Evripidis Bampis, Laurent Gourvs |