| 2003 | 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 7-10 July 2003, Aarhus, Denmark |
| 2003 | A Combinatorial Characterization of Resolution Width. Albert Atserias, Víctor Dalmau |
| 2003 | A Strong Inapproximability Gap for a Generalization of Minimum Bisection. Jonas Holmerin, Subhash Khot |
| 2003 | A zero one law for RP. Russell Impagliazzo, Philippe Moser |
| 2003 | Are Cook and Karp Ever the Same? Richard Beigel, Lance Fortnow |
| 2003 | Bounded Nondeterminism and Alternation in Parameterized Complexity Theory. Yijia Chen, Jörg Flum, Martin Grohe |
| 2003 | Derandomization and Distinguishing Complexity. Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy |
| 2003 | Disjoint NP-Pairs. Christian Glaßer, Alan L. Selman, Samik Sengupta, Liyu Zhang |
| 2003 | Extracting the Mutual Information for a Triple of Binary Strings. Andrei Romashchenko |
| 2003 | Extremal properties of polynomial threshold functions. Ryan O'Donnell, Rocco A. Servedio |
| 2003 | Hardness vs. Randomness within Alternating Time. Emanuele Viola |
| 2003 | Holographic Proofs and Derandomization. Rahul Santhanam, Dieter van Melkebeek |
| 2003 | Improved Inapproximability of Lattice and Coding Problems with Preprocessing. Oded Regev |
| 2003 | Inapproximability Some history and some open problems. Johan Håstad |
| 2003 | List Decoding with Side Information. Venkatesan Guruswami |
| 2003 | Lower bounds for predecessor searching in the cell probe model. Pranab Sen |
| 2003 | Memoization and DPLL: Formula Caching Proof Systems. Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind |
| 2003 | Minimization of Decision Trees Is Hard to Approximate. Detlef Sieling |
| 2003 | Near-Optimal Lower Bounds on the Multi-Party Communication Complexity of Set Disjointness. Amit Chakrabarti, Subhash Khot, Xiaodong Sun |
| 2003 | On Derandomizing Tests for Certain Polynomial Identities. Manindra Agrawal |
| 2003 | On Statistical Query Sampling and NMR Quantum Computing. Ke Yang, Avrim Blum |
| 2003 | Optimal Separation of EROW and CROWPRAMs. Navin Goyal, Michael E. Saks, Srinivasan Venkatesh |
| 2003 | Proving SAT does not have Small Circuits with an Application to the Two. Lance Fortnow, Aduri Pavan, Samik Sengupta |
| 2003 | Quantum Certificate Complexity. Scott Aaronson |
| 2003 | Quantum query complexity and semi-definite programming. Howard Barnum, Michael E. Saks, Mario Szegedy |
| 2003 | Rectangle Size Bounds and Threshold Covers in Communication Complexity. Hartmut Klauck |
| 2003 | The Complexity of Unique k-SAT: An Isolation Lemma for k-CNFs. Chris Calabro, Russell Impagliazzo, Valentine Kabanets, Ramamohan Paturi |
| 2003 | The complexity of stochastic sequences. Wolfgang Merkle |
| 2003 | Three-Query PCPs with Perfect Completeness over non-Boolean Domains. Lars Engebretsen, Jonas Holmerin |
| 2003 | Uniform hardness vs. randomness tradeoffs for Arthur-Merlin games. Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma |
| 2003 | Universal Languages and the Power of Diagonalization. Alan Nash, Russell Impagliazzo, Jeffrey B. Remmel |
| 2003 | Vertex Cover Might be Hard to Approximate to within 2-\varepsilon. Subhash Khot, Oded Regev |