| 2003 | 44th Symposium on Foundations of Computer Science, FOCS 2003, Cambridge, MA, USA, October 11-14, 2003, Proceedings |
| 2003 | A Group-Theoretic Approach to Fast Matrix Multiplication. Henry Cohn, Christopher Umans |
| 2003 | A Lattice Problem in Quantum NP. Dorit Aharonov, Oded Regev |
| 2003 | A Lower Bound for the Bounded Round Quantum Communication Complexity of Set Disjointness. Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen |
| 2003 | A Non-Markovian Coupling for Randomly Sampling Colorings. Thomas P. Hayes, Eric Vigoda |
| 2003 | A Polynomial Algorithm for Recognizing Perfect Graphs. Gérard Cornuéjols, Xinming Liu, Kristina Vuskovic |
| 2003 | Algorithms and Complexity Results for #SAT and Bayesian Inference. Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi |
| 2003 | Always Good Turing: Asymptotically Optimal Probability Estimation. Alon Orlitsky, Narayana P. Santhanam, Junan Zhang |
| 2003 | An In-Place Sorting with O(n log n) Comparisons and O(n) Moves. Gianni Franceschini, Viliam Geffert |
| 2003 | Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs. Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko |
| 2003 | Approximation Algorithms for Orienteering and Discounted-Reward TSP. Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, Maria Minkoff |
| 2003 | Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem. Anupam Gupta, Amit Kumar, Martin Pál, Tim Roughgarden |
| 2003 | Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm. Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schäfer, Tjark Vredeveld |
| 2003 | Bounded Geometries, Fractals, and Low-Distortion Embeddings. Anupam Gupta, Robert Krauthgamer, James R. Lee |
| 2003 | Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds. Rafael Pass, Alon Rosen |
| 2003 | Breaking a Time-and-Space Barrier in Constructing Full-Text Indices. Wing-Kai Hon, Kunihiko Sadakane, Wing-Kin Sung |
| 2003 | Broadcasting Algorithms in Radio Networks with Unknown Topology. Artur Czumaj, Wojciech Rytter |
| 2003 | Clustering with Qualitative Information. Moses Charikar, Venkatesan Guruswami, Anthony Wirth |
| 2003 | Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. Jesse Kamp, David Zuckerman |
| 2003 | General Composition and Universal Composability in Secure Multi-Party Computation. Yehuda Lindell |
| 2003 | Gossip-Based Computation of Aggregate Information. David Kempe, Alin Dobra, Johannes Gehrke |
| 2003 | Group Strategyproof Mechanisms via Primal-Dual Algorithms. Martin Pál, Éva Tardos |
| 2003 | Hardness of Approximating the Shortest Vector Problem in High L Subhash Khot |
| 2003 | I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs. Lars Arge, Norbert Zeh |
| 2003 | Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model. Rajat Bhattacharjee, Ashish Goel |
| 2003 | Learning DNF from Random Walks. Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio |
| 2003 | Linear Upper Bounds for Random Walk on Small Density Random 3-CNF. Michael Alekhnovich, Eli Ben-Sasson |
| 2003 | List-Decoding Using The XOR Lemma. Luca Trevisan |
| 2003 | Locally Testable Cyclic Codes. László Babai, Amir Shpilka, Daniel Stefankovic |
| 2003 | Logconcave Functions: Geometry and Efficient Sampling Algorithms László Lovász, Santosh S. Vempala |
| 2003 | Logics for Reasoning about Cryptographic Constructions. Russell Impagliazzo, Bruce M. Kapron |
| 2003 | Lower Bounds for Non-Black-Box Zero Knowledge. Boaz Barak, Yehuda Lindell, Salil P. Vadhan |
| 2003 | Machine Learning: My Favorite Results, Directions, and Open Problems. Avrim Blum |
| 2003 | Mixing. Dana Randall |
| 2003 | More on Average Case vs Approximation Complexity. Michael Alekhnovich |
| 2003 | On Certain Connectivity Properties of the Internet Topology. Milena Mihail, Christos H. Papadimitriou, Amin Saberi |
| 2003 | On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences. Timothy M. Chan |
| 2003 | On Worst-Case to Average-Case Reductions for NP Problems. Andrej Bogdanov, Luca Trevisan |
| 2003 | On e-Biased Generators in NC0. Elchanan Mossel, Amir Shpilka, Luca Trevisan |
| 2003 | On the (In)security of the Fiat-Shamir Paradigm. Shafi Goldwasser, Yael Tauman Kalai |
| 2003 | On the Implementation of Huge Random Objects. Oded Goldreich, Shafi Goldwasser, Asaf Nussboim |
| 2003 | On the Impossibility of Dimension Reduction in l Bo Brinkman, Moses Charikar |
| 2003 | On the Maximum Satisfiability of Random Formulas. Dimitris Achlioptas, Assaf Naor, Yuval Peres |
| 2003 | Paths, Trees, and Minimum Latency Tours. Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, Kunal Talwar |
| 2003 | Performance Analysis of Dynamic Network Processes. Eli Upfal |
| 2003 | Polynomial Degree vs. Quantum Query Complexity. Andris Ambainis |
| 2003 | Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the Finite Random Assignment Problem. Chandra Nair, Balaji Prabhakar, Mayank Sharma |
| 2003 | Proving Hard-Core Predicates Using List Decoding. Adi Akavia, Shafi Goldwasser, Shmuel Safra |
| 2003 | Quantum Search of Spatial Regions. Scott Aaronson, Andris Ambainis |
| 2003 | Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua. Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi |
| 2003 | Separating the Power of Monotone Span Programs over Different Fields. Amos Beimel, Enav Weinreb |
| 2003 | Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm. László Lovász, Santosh S. Vempala |
| 2003 | Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time 0(m Daniel A. Spielman, Shang-Hua Teng |
| 2003 | Stability and Efficiency of a Random Local Load Balancing Protocol. Aris Anagnostopoulos, Adam Kirsch, Eli Upfal |
| 2003 | Switch Scheduling via Randomized Edge Coloring. Gagan Aggarwal, Rajeev Motwani, Devavrat Shah, An Zhu |
| 2003 | Symmetric Polynomials over Z Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton |
| 2003 | The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side. Martin Grohe |
| 2003 | The Cost of Cache-Oblivious Searching. Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono, Alejandro López-Ortiz |
| 2003 | The Ising Model on Trees: Boundary Conditions and Mixing Time. Fabio Martinelli, Alistair Sinclair, Dror Weitz |
| 2003 | The Resolution Complexity of Random Constraint Satisfaction Problems. Michael Molloy, Mohammad R. Salavatipour |
| 2003 | The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions. Robert D. Kleinberg, Frank Thomson Leighton |
| 2003 | Tight Lower Bounds for the Distinct Elements Problem. Piotr Indyk, David P. Woodruff |
| 2003 | Towards a Characterization of Truthful Combinatorial Auctions. Ron Lavi, Ahuva Mu'alem, Noam Nisan |
| 2003 | Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem. Andrei A. Bulatov, Víctor Dalmau |
| 2003 | Zero-Knowledge Sets. Silvio Micali, Michael O. Rabin, Joe Kilian |