List of accepted papers for STOC 2003: The worst-case behavior of Schnorr's algorithm approximating the shortest nonzero vector in a lattice Miklos Ajtai Random Knapsack in Expected Polynomial Time Rene Beier and Berthold Voecking A Proof of Alon's Second Eigenvalue Conjecture Joel Friedman Integer priority queues with decrease key in constant time and the single source shortest paths problem Mikkel Thorup Testing Subgraphs in Directed Graphs Noga Alon and Asaf Shapira Bounds on the Efficiency of Encryption and Digital Signatures Rosario Gennaro and Yael Gertner and Jonathan Katz Derandomizing polynomial identity tests means proving circuit lower bounds Valentine Kabanets and Russell Impagliazzo Polylogarithmic inapproximability Eran Halperin and Robert Krauthgamer Uniform Hashing in Constant Time and Linear Space Anna Östlin and Rasmus Pagh Optimal oblivious routing in polynomial time Yossi Azar and Edith Cohen and Amos Fiat and Haim Kaplan and Harald Raecke Exponential algorithmic speedup by a quantum walk Andrew Childs and Richard Cleve and Enrico Deotto and Edward Farhi and Sam Gutmann and Daniel Spielman Reconstructing curves in three (and higher) dimensional space from noisy data Don Coppersmith and Madhu Sudan The intrinsic dimensionality of graphs Robert Krauthgamer and James R. Lee Exponential lower bound for 2-query locally decodable codes via a quantum argument Iordanis Kerenidis and Ronald de Wolf Quantum Time-Space Tradeoffs for Sorting Hartmut Klauck Learning juntas Elchanan Mossel, Rocco Servedio, Ryan O'Donnell New degree bounds on polynomial threshold functions Ryan O'Donnell, Rocco Servedio Consistent Load Balancing Via Spread Minimization Robert D. Kleinberg and F. Thomson Leighton Approximate counting by dynamic programming Martin Dyer Primal-dual algorithms come of age: Approximating MST's with nonuniform degree bounds J. Konemann and R. Ravi Sublinear Geometric Algorithms Bernard Chazelle and Ding Liu and Avner Magen Optimal probabilistic fingerprint codes Gabor Tardos On the Power of Quantum Fingerprinting Andrew Chi-Chih Yao Approximation Schemes for Clustering Problems W. Fernandez de la Vega "and" Marek Karpinski "and" Claire Kenyon "and" Yuval Rabani The Online Set Cover Problem Noga Alon and Baruch Awerbuch and Yossi Azar and Niv Buchbinder and Joseph (Seffi) Naor Management of Multi-Queue Switches In QoS Networks Yossi Azar and Yossi Richter 3CNF Properties are Hard to Test Eli Ben-Sasson and Prahladh Harsha and Sofya Raskhodnikova On Metric Ramsey-Type Phenomena Yair Bartal and Nathan Linial and Manor Mendel and Assaf Naor Evolving sets and mixing Ben Morris and Yuval Peres Cutting Triangular Cycles of Lines in Space Boris Aronov and Vladlen Koltun and Micha Sharir Server Scheduling in the L_p Norm: A Rising Tide Lifts All Boats Nikhil Bansal and Kirk Pruhs A New Approach to Dynamic All Pairs Shortest Paths C. Demetrescu and G.F. Italiano Near-Optimal Network Design with Selfish Agents Elliot Anshelevich and Anirban Dasgupta and Eva Tardos and Tom Wexler Distinct Distances in Three and Higher Dimensions Boris Aronov and J\'anos Pach and Micha Sharir and G\'abor Tardos Modified log-Sobolev inequalities, mixing and hypercontractivity Sergey Bobkov and Prasad Tetali Better Streaming Algorithms for Clustering Problems Moses Charikar and Liadan O'Callaghan and Rina Panigrahy New Lattice Based Cryptographic Constructions Oded Regev A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover Irit Dinur and Venkatesan Guruswami and Subhash Khot and Oded Regev On the Fractal Behavior of TCP Anna C. Gilbert and Howard Karloff Linear time encodable and list decodable codes Venkatesan Guruswami and Piotr Indyk Lower bounds on the amount of randomness in private computation Anna Gal and Adi Rosen OPT versus LOAD in Dynamic Storage Allocation Adam L. Buchsbaum and Howard Karloff and Claire Kenyon and Nick Reingold and Mikkel Thorup On the Sample Size of k-Restricted Min-Wise Independent and Other k-Wise Distributions Toshiya Itoh, Yoshinori Takei, Jun Tarui Dynamic rectangular intersection with priorities Haim Kaplan and Eyal Molad and Robert E. Tarjan Hidden Translation and Orbit Coset in Quantum Computing Katalin Friedl and Gabor Ivanyos and Frederic Magniez and Miklos Santha and Pranab Sen Pricing Network Edges for Heterogeneous Selfish Users Richard Cole and Yevgeniy Dodis and Tim Roughgarden Simpler and Better Approximation Algorithms for Network Design Anupam Gupta and Amit Kumar and Tim Roughgarden Cell probe lower bounds for the partial match problem T. S. Jayram and Subhash Khot and Ravi Kumar and Yuval Rabani Short Path Queries in Planar Graphs in Constant Time Lukasz Kowalik and Maciej Kurowski Boosting in the presence of noise Adam Kalai and Rocco A. Servedio Two applications of information complexity T. S. Jayram and Ravi Kumar and D. Sivakumar Touring a Sequence of Polygons Moshe Dror and Alon Efrat and Anna Lubiw and Joseph S. B. Mitchell Bounded-Concurrent Secure Two-Party Computation Without Setup Assumptions Yehuda Lindell The Computational Complexity of Some Julia Sets Robert Rettinger and Klaus Weihrauch Non-interactive and Reusable Non-malleable Commitment Schemes Ivan Damgaard and Jens Groth Reducing Truth-telling Online Mechanisms to Online Optimization Baruch Awerbuch, Yossi Azar, and Adam Meyerson A Fast Algorithm for Computing Edge Connectivity of Steiner Points Richard Cole and Ramesh Hariharan Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and its Applications Jie Gao and Li Zhang On the Limits of Cache-Obliviousness Gerth Stølting Brodal and Rolf Fagerberg Work-Competitive Scheduling for Cooperative Computing with Dynamic Groups Chryssis Georgiou and Alexander Russell and Alex A. Shvartsman Derandomizing low degree tests via epsilon-biased spaces Eli Ben-Sasson and Madhu Sudan and Salil Vadhan and Avi Wigderson A Tight Time Lower Bound for Space-Optimal Implementations of Multi-Writer Snapshots Panagiota Fatourou and Faith Fich and Eric Ruppert Space efficient dynamic stabbing with fast queries Mikkel Thorup Extractors: Optimal Up to Constant Factors Chi-Jen Lu and Omer Reingold and Salil Vadhan and Avi Wigderson Classical deterministic complexity of Edmonds' problem and Quantum Entanglement Leonid Gurvits Time-Space Tradeoff Lower Bounds for Integer Multiplication and Graphs of Arithmetic Functions Martin Sauerhoff and Philipp Woelfel Almost random graphs with simple hash functions Martin Dietzfelbinger and Philipp Woelfel On Average Distortion of Embedding Metrics into $l_1$ and into the Line Yuri Rabinovich Sampling Lower Bounds via Information Theory Ziv Bar-Yossef A stochastic process on the hypercube with applications to peer-to-peer networks Micah Adler and Eran Halperin and Richard M. Karp and Vijay V. Vazirani Meet and Merge: Approximation Algorithms for Confluent Flows Jiangzhuo Chen and Rajmohan Rajaraman and Ravi Sundaram A sublinear algorithm for weakly approximating edit distance Tugkan Batu and Funda Ergun and Joe Kilian and Avner Magen and Sofya Raskhodnikova and Ronitt Rubinfeld and Rahul Sami $\alpha$-Shapes and Flow Shapes are Homotopy Equivalent Tamal K. Dey, Joachim Giesen, Matthias John A tight bound on approximating arbitrary metrics by tree metrics Jittat Fakcharoenphol and Satish Rao and Kunal Talwar Randomly coloring graphs of girth at least five Thomas P. Hayes The Threshold for Random k-SAT is 2^k (ln 2 + o(1)) Dimitris Achlioptas and Yuval Peres Sampling Uniform Random Regular Graphs J.H. Kim and V.H. Vu Constant factor approximation of vertex-cuts in planar graphs Eyal Amir and Robert Krauthgamer and Satish Rao Adiabatic Quantum State Generation and Statistical Zero Knowledge Dorit Aharonov and Amnon Ta-Shma Approximation Algorithms for Hierarchical Location Problems C. Greg Plaxton