Papers accepted to STOC 2004 (in the order they were submitted):
--------------------------

Lower Bounds for Local Search by Quantum Arguments
Scott Aaronson

On sums of independent random variables with unbounded variance, and estimating the average degree in a graph.
Uriel Feige

Approximating the Cut-Norm via Grothendieck's Inequality
Noga Alon, Assaf Naor

Counting Complexity Classes for Numeric Computations II:Algebraic and Semialgebraic Sets
Peter Buergisser, Felipe Cucker

Graph Entropy and Quantum Sorting Problems
Andrew Yao

Approximating k-node connected subgraphs via critical graphs
Guy Kortsarz, Zeev Nutov

The difficulty of testing for isomorphism against a graph that is given in advance
Eldar Fischer

Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size
Ran Raz

A Conjecture about Polynomial Time Computable Lattice-Lattice Functions
Miklos Ajtai

Completeness in Two-Party Secure Computation - A Computational View
Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen

Robust PCPs of Proximity, Shorter PCPs and Applications to Coding
Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan

An approximate Konig's theorem for edge coloring weighted bipartite graphs
Jose Correa, Michel Goemans

Sharp thresholds for monotone properties in random geometric graphs
Ashish Goel, Sanatan Rai, Bhaskar Krishnamachari

Multilinear Formulas and Skepticism of Quantum Computing
Scott Aaronson

Coresets for k-Means and k-Median Clustering and their Applications
Sariel Har-Peled, Soham Mazumdar

On the Performance of Greedy Algorithms in Packet Buffering
Susanne Albers, Markus Schmidt

Concurrent flows in O(1/epsilon) time
Daniel Bienstock, Garud Iyengar

Boosted Sampling: Approximation Algorithms for Stochastic Optimization
Anupam Gupta, Martin Pal, R. Ravi, Amitabh Sinha

A New PCP Outer Verifier with Applications to Homogeneous Linear Equations and Max-Bisection
Jonas Holmerin, Subhash Khot

Adaptive Routing with End-to-End feedback: Distributed Learning and Geometric Approaches
Baruch Awerbuch, Robert Kleinberg

The All-or-Nothing Multicommodity Flow Problem
Chandra Chekuri, Sanjeev Khanna, Bruce Shepherd

Isotopic implicit surface meshing
Jean-Daniel Boissonnat, David Cohen-Steiner, Gert Vegter

Algorithms for Dynamic Geometric Problems over Data Streams
Piotr Indyk

The Spending Constraint Model for Market Equilibrium: Algorithmic, Existence and Uniqueness results
Nikhil Devanur, Vijay Vazirani

Better Extractors for Better Codes?
Venkatesan Guruswami

Collective Asynchronous Reading with Polylogarithmic Worst-Case Overhead
Bogdan Chlebus, Dariusz Kowalski, Alexander Shvartsman

Exponential separation of quantum and classical one-way communication complexity
Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis

The quantum adiabatic optimization algorithm and local minima
Ben Reichardt

Approximate max-integral-flow/min-multicut theorems
Kenji Obata

A fully dynamic reachability algorithm for directed graphs with an almost linear update time
Liam Roditty, Uri Zwick

Sorting and searching in the presence of memory faults (without redundancy)
Irene Finocchi, Giuseppe F. Italiano

Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus
Jonathan Kelner

Derandomizing Homomorphism Testing in General Groups
Amir Shpilka, Avi Wigderson

The zero-one principle for switching networks
Yossi Azar, Yossi Richter

Hit-and-run from a corner
Laszlo Lovasz, Santosh Vempala

Primal-Dual Algorithms for Deterministic Inventory Problems
Retsef Levi, Robin Roundy, David Shmoys

Typical Properties of Winners and Losers in Discrete Optimization
Rene Beier, Berthold Voecking

Asymmetric K-Center is log* n Hard to Approximate
Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor

Low Distortion Maps Between Point Sets
Claire Kenyon, Yuval Rabani, Alistair Sinclair

Bounded-Concurrent Secure Multi-Party Computation with a Dishonest Majority
Rafael Pass

A Simple Polynomial-time Rescaling Algorithm for Solving Linear Programs
John Dunagan, Santosh Vempala

(Almost) Tight Bounds and Existence Theorems for Confluent Flows
Jiangzhuo Chen, Robert Kleinberg, Laszlo Lovasz, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta

Auction Algorithms for Market Equilibrium
Sanjiv Kapoor, Rahul Garg

Approximation Algorithms for Deadline-TSP
Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson

Computing Nash Equilibria for Scheduling on Restricted Parallel Links
Martin Gairing, Thomas Luecking, Marios Mavronicolas, Burkhard Monien

Know Thy Neighbor's Neighbor: The Power of Lookahead in Randomized P2P Networks
Gurmeet Manku, Moni Naor, Udi Wieder

Multi-processor Scheduling for Minimizing Flow Time with $\eps$ Resource Augmentation
Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar

Linear FPT Reductions and Computational Lower Bounds
Jianer Chen, Xiuzhen Huang, Iyad Kanj, Ge Xia

Lower Bounds for Dynamic Connectivity
Mihai Patrascu, Erik Demaine

Finding Paths and Cycles of Superpolylogarithmic Length
Harold Gabow

Rational Secret Sharing and Multiparty Computation
Joseph Halpern, Vanessa Teague

Using Nondeterminism to Amplify Hardness
Alexander Healy, Salil Vadhan, Emanuele Viola

Quantum and Classical Query Complexities ofLocal Search are Polynomially Related
Miklos Santha, Mario Szegedy

Using Mixture Models for Collaborative Filtering
Jon Kleinberg, Mark Sandler

A new family of Cayley expanders (?)
Eyal Rozenman, Aner Shalev, Avi Wigderson

New Hardness Results for Congestion Minimization and Machine Scheduling
Julia Chuzhoy, Joseph Naor

A Decentralized Algorithm for Spectral Analysis
David Kempe, Frank McSherry

Estimating the Weight of Metric Minimum Spanning Trees in Sublinear-Time
Artur Czumaj, Christian Sohler

Bypassing the Embedding: Approximation schemes and distance labelings for growth restricted metrics
Kunal Talwar

Batch Codes and Their Applications
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai

The Two Possible Values of the Chromatic Number of a Random Graph
Dimitris Achlioptas, Assaf Naor

Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems
Daniel Spielman, Shang-Hua Teng

New Notions of Security: Achieving Universal Composability without Trusted Setup
Manoj Prabhakaran, Amit Sahai

Expander flows and a sqrt{log n}-approximation to sparsest cut
Sanjeev Arora, Satish Rao, Umesh Vazirani

Visibly Pushdown Languages
Rajeev Alur, P. Madhusudan

Lower Bounds for Linear Degeneracy Testing
Nir Ailon, Bernard Chazelle

The Complexity of Pure Nash Equilibria
Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar

Sublinear algorithms for testing monotone and unimodal distributions
Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld

Unconditional Lower Bounds on the Time-Approximation Tradeoffs for the Distributed Minimum Spanning Tree Problem
Michael Elkin

Dictionary matching and indexing with errors and don't cares
Richard Cole, Lee-Ad Gottlieb, Moshe Lewenstein