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