| 2003 | Adaptive and Compact Discretization for Weighted Region Optimal Path Finding. Zheng Sun, John H. Reif |
| 2003 | An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates. Ivan Damgård, Gudmund Skovbjerg Frandsen |
| 2003 | An Improved Analysis of Goemans and Williamson's LP-Relaxation for MAX SAT. Takao Asano |
| 2003 | An Improved Approximation Algorithm for Computing Geometric Shortest Paths. Lyudmil Aleksandrov, Anil Maheshwari, Jörg-Rüdiger Sack |
| 2003 | Approximating the Pareto Curve with Local Search for the Bicriteria TSP (1, 2) Problem. Eric Angel, Evripidis Bampis, Laurent Gourvès |
| 2003 | Baire's Categories on Small Complexity Classes. Philippe Moser |
| 2003 | Certifying Unsatisfiability of Random 2 Amin Coja-Oghlan, Andreas Goerdt, André Lanka, Frank Schädlich |
| 2003 | Circuits on Cylinders. Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay |
| 2003 | Classical Simulation Complexity of Quantum Machines. Farid M. Ablayev, Aida Gainutdinova |
| 2003 | Competitive Exploration of Rectilinear Polygons. Mikael Hammar, Bengt J. Nilsson, Mia Persson |
| 2003 | Complexity of Approximating Closest Substring Problems. Patricia A. Evans, Andrew D. Smith |
| 2003 | Composing Equipotent Teams. Mark Cieliebak, Stephan J. Eidenbenz, Aris Pagourtzis |
| 2003 | Compositionality of Hennessy-Milner Logic through Structural Operational Semantics. Wan J. Fokkink, Rob J. van Glabbeek, Paulien de Wind |
| 2003 | Constructing Sparse t-Spanners with Small Separators. Joachim Gudmundsson |
| 2003 | Context-Sensitive Equivalences for Non-interference Based Protocol Analysis. Michele Bugliesi, Ambra Ceccato, Sabina Rossi |
| 2003 | Dimension- and Time-Hierarchies for Small Time Bounds. Martin Kutrib |
| 2003 | Efficient Algorithms for GCD and Cubic Residuosity in the Ring of Eisenstein Integers. Ivan Damgård, Gudmund Skovbjerg Frandsen |
| 2003 | Fast Perfect Phylogeny Haplotype Inference. Peter Damaschke |
| 2003 | Fast Periodic Correction Networks. Grzegorz Stachowiak |
| 2003 | Fundamentals of Computation Theory, 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings Andrzej Lingas, Bengt J. Nilsson |
| 2003 | Games and Networks. Christos H. Papadimitriou |
| 2003 | Graph Searching, Elimination Trees, and a Generalization of Bandwidth. Fedor V. Fomin, Pinar Heggernes, Jan Arne Telle |
| 2003 | Inapproximability Results for Bounded Variants of Optimization Problems. Miroslav Chlebík, Janka Chlebíková |
| 2003 | Kleene's Theorem for Weighted Tree-Automata. Christian Pech |
| 2003 | Languages Defined by Generalized Equality Sets. Vesa Halava, Tero Harju, Hendrik Jan Hoogeboom, Michel Latteux |
| 2003 | Linear Time Algorithms for Some NP-Complete Problems on (P Hans L. Bodlaender, Andreas Brandstädt, Dieter Kratsch, Michaël Rao, Jeremy P. Spinrad |
| 2003 | Membrane Computing. Gheorghe Paun |
| 2003 | Non-uniform Depth of Polynomial Time and Space Simulations. Richard J. Lipton, Anastasios Viglas |
| 2003 | On Boundaries of Highly Visible Spaces and Applications. John H. Reif, Zheng Sun |
| 2003 | On Exact and Approximation Algorithms for Distinguishing Substring Selection. Jens Gramm, Jiong Guo, Rolf Niedermeier |
| 2003 | On Lawson's Oriented Walk in Random Delaunay Triangulations. Binhai Zhu |
| 2003 | On a Logical Approach to Estimating Computational Complexity of Potentially Intractable Problems. Andrzej Szalas |
| 2003 | On the Exponentiation of Languages. Werner Kuich, Klaus W. Wagner |
| 2003 | One-Way Communication Complexity of Symmetric Boolean Functions. Jan Arpe, Andreas Jakoby, Maciej Liskiewicz |
| 2003 | Operations Preserving Recognizable Languages. Jean Berstel, Luc Boasson, Olivier Carton, Bruno Petazzoni, Jean-Eric Pin |
| 2003 | Periodic Multisorting Comparator Networks. Marcin Kik |
| 2003 | Proving Integrality Gaps without Knowing the Linear Program. Sanjeev Arora |
| 2003 | Scheduling to Minimize Max Flow Time: Offline and Online Algorithms. Monaldo Mastrolilli |
| 2003 | Using Depth to Capture Average-Case Complexity. Luis Antunes, Lance Fortnow, N. V. Vinodchandran |
| 2003 | Weak Cardinality Theorems for First-Order Logic. Till Tantau |