FOCS 2003: List of accepted papers. ----------------------------------- Perfect Graph Recognition Gerard Cornuejols and Xinming Liu and Kristina Vuskovic Quantum Search of Spatial Regions Scott Aaronson and Andris Ambainis Hardness of Approximating the Shortest Vector Problem in High L_p Subhash Khot An In-Place Sorting with O(n log n) Comparisons and O(n) Moves Gianni Franceschini and Viliam Geffert Logics for reasoning about cryptographic constructions Russell Impagliazzo AND Bruce M. Kapron On the Implementation of Huge Random Objects Oded Goldreich and Shafi Goldwasser and Asaf Nussboim Smoothening Helps: A Probabilistic Analysis of the Multi-Level Feedback Algorithm Luca Becchetti and Stefano Leonardi and Alberto Marchetti-Spaccamela and Guido Schaefer and Tjark Vredeveld Learning DNF from Random Walks Nader Bshouty and Elchanan Mossel and Ryan O'Donnell and Rocco Servedio The complexity of homomorphism and constraint satisfaction problems seen from the other side Martin Grohe Safraless Decision Procedures Orna Kupferman and Moshe Y. Vardi Locally Testable Cyclic Codes Laszlo Babai and Amir Shpilka and Daniel Stefankovic List Decoding Using the XOR Lemma Luca Trevisan Instability of FIFO at Arbitrarily Low Rates in the Adversarial Bhattacharjee, R. and Goel, A. Breaking a Time-and-Space Barrier in Constructing Full-Text Indices Wing-Kai Hon and Kunihiko Sadakane and Wing-Kin Sung Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the Chandra Nair and Balaji Prabhakar and Mayank Sharma Separating the Power of Monotone Span Programs over Different Fields Amos Beimel and Enav Weinreb A 2/3 Approximation for Maximum Asymmetric TSP by Decomposing Directed Regular Multigraphs Haim Kaplan and Moshe Lewenstein and Nira Shafrir and Maxim Sviridenko On the Impossibility of Dimension Reduction in $\ell_1$ Bo Brinkman and Moses Charikar Stability and Efficiency of a Random Local Load Balancing Protocol Aris Anagnostopoulos and Adam Kirsch and Eli Upfal An $\epsilon$-Biased Generator in NC^0 Elchanan Mossel and Amir Shpilka and Luca Trevisan A group-theoretic approach to fast matrix multiplication Henry Cohn and Christopher Umans The Ising model on trees: Boundary conditions and mixing time Fabio Martinelli and Alistair Sinclair and Dror Weitz Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography Jesse Kamp and David Zuckerman Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem Anupam Gupta and Amit Kumar and Martin Pal and Tim Roughgarden Clustering with Qualitative Information Moses Charikar and Venkatesan Guruswami and Anthony Wirth The resolution complexity of random constraint satisfaction problems Michael Molloy and Mohammad Salavatipour Towards a Characterization of Truthful Combinatorial Auctions Ron Lavi and Ahuva Mu'alem and Noam Nisan Bounded geometries, fractals, and low--distortion embeddings Anupam Gupta and Robert Krauthgamer and James R. Lee Strategy Proof Mechanisms via Primal-Dual Algorithms Martin Pal and Eva Tardos On Worst-Case to Average-Case Reductions for NP Problems Andrej Bogdanov and Luca Trevisan Towards a dichotomy theorem for the Counting Constraint Satisfaction Problem Andrei A. Bulatov and Victor Dalmau Approximation Algorithms for Orienteering and Discounted-Reward TSP Avrim Blum and Shuchi Chawla and David Karger and Terran Lane and Adam Meyerson and Maria Minkoff The Value of Knowing a Demand Curve: Bounds on Regret for On-Line Posted-Price Auctions Robert Kleinberg and Tom Leighton A Lattice Problem in Quantum NP Dorit Aharonov and Oded Regev Zero-Knowledge Sets Silvio Micali and Michael Rabin and Joe Kilian On the (In)security of the Fiat-Shamir Paradigm Shafi Goldwasser and Yael Tauman Solving Sparse SPDDD Linear Systems in Time O(m^1.31) Daniel Spielman and Shang-Hua Teng Gossip-Based Computation of Aggregate Information David Kempe and Alin Dobra and Johannes Gehrke Logconcave Functions: Geometry and Efficient Sampling Algorithms Laszlo Lovasz and Santosh Vempala A Unifying Approach for Proving Hardcore Predicates Using List Decoding Adi Akavia and Shafi Goldwasser and Muli Safra I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs Lars Arge and Norbert Zeh Algorithms and Complexity Results for sharpSAT and Bayesian Inference Fahiem Bacchus and Shannon Dalmao and Toniann Pitassi Linear Upper Bounds for Random Walk on Small Density Random 3-CNFs Mikhail Alekhnovich and Eli Ben-Sasson Simulated Annealing in Convex Bodies and an O*(n^4) Volume Algorithm Laszlo Lovasz and Santosh Vempala A lower bound for bounded round quantum communication complexity of set disjointness Rahul Jain and Jaikumar Radhakrishnan and Pranab Sen Broadcasting Algorithms in Radio Networks with Unknown Topology Artur Czumaj and Wojciech Rytter On Certain Connectivity Properties of the Internet Topology Milena Mihail and Christos Papadimitriou and Amin Saberi Polynomial degree vs. quantum query complexity Andris Ambainis On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences Timothy M. Chan Lower Bounds for Non-Black-Box Zero Knowledge Boaz Barak, Yehuda Lindell, Salil Vadhan Paths, Trees and minimum latency tours Kamalika Chaudhuri and Brighten Godfrey and Satish Rao and Kunal Talwar More on average case vs approximation complexity Michael Alekhnovich A Non-Markovian Coupling for Randomly Sampling Colorings Thomas P. Hayes and Eric Vigoda Switch Scheduling via Randomized Edge Coloring Gagan Aggarwal and Rajeev Motwani and Devavrat Shah and An Zhu The Cost of Cache-Oblivious Searching Michael A. Bender and Gerth St\o{}lting Brodal and Rolf Fagerberg and Dongdong Ge and Simai He and Haodong Hu and John Iacono and Alejandro L\'{o}pez-Ortiz On the Maximum Satisfiability of Random Formulas Dimitris Achlioptas and Assaf Naor and Yuval Peres General Composition and Universal Composability in Secure Yehuda Lindell Bounded-Concurrent Secure Two-Party Computation in a Constant Rafael Pass and Alon Rosen Representing Boolean Functions by Symmetric Polynomials Nayantara Bhatnagar and Parikshit Gopalan and Richard J. Lipton On the Rank of Cutting Planes Proof-Systems and the Role of Josh Buresh-Oppenheim and Nicola Galesi and Shlomo Hoory and Tight Lower Bounds for the Distinct Elements Problem Piotr Indyk and David Woodruff Better Turing: asymptotically optimal probability estimation Alon Orlitsky and Narayana P. Santhanam and Junan Zhang