List of accepted papers for STOC 2004: 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, Umesh Vazirani 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 Multiple-source shortest paths in planar graphs allowing negative lengths Philip Klein 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, 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 Chromatic Number of G(n,d/n) is... Dimitris Achlioptas, Assaf Naor Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems Daniel Spielman, Shang-Hua Teng Universal Composability in the Standard Model with Relaxed Notions of Security 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