Accepted papers to STOC 2003 (in the order they were submitted):

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