Accepted papers for FOCS 2004, sorted in submission order. Lattice problems in NP intersect coNP Dorit Aharonov and Oded Regev An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching Amit Chakrabarti and Oded Regev On the Power of Discrete and of Lexicographic Helly-Type Theorems Nir Halman Strong Spatial Mixing for Lattice Graphs with Fewer Colours Leslie Ann Goldberg and Russell Martin and Mike Paterson Hardness of Approximating the Shortest Vector Problem in Lattices Subhash Khot Randomly coloring constant degree graphs Alan M. Frieze No Sorting? Better Searching! Gianni Franceschini and Roberto Grossi Dynamic Speed Scaling to Manage Energy and Temperature Nikhil Bansal, Tracy Kimbrel and Kirk Pruhs Holographic Algorithms Leslie G. Valiant Maximizing quadratic programs: extending Grothendieck's inequality Moses Charikar and Anthony Wirth Quantum weak coin-flipping with bias of 0.192 Carlos Mochon Testing Polynomials over General Fields Tali Kaufman and Dana Ron Quantum and classical strong direct product theorems and optimal time-space tradeoffs Hartmut Klauck and Robert Spalek and Ronald de Wolf Shuffling by semi-random transpositions Elchanan Mossel and Yuval Peres and Alistair Sinclair Measured descent: A new embedding method for finite metrics R. Krauthgamer and J. R. Lee and M. Mendel and A. Naor Learning with Errors in Answers to Membership Queries Nader Bshouty An approximate max-Steiner-tree-packing min-Steiner-cut theorem Lap Chi Lau Hierarchy Theorems for Probabilistic Polynomial Time Lance Fortnow and Rahul Santhanam A Simple linear time (1+$\varepsilon$)-approximation algorithm for k-means clustering in any dimensions Amit Kumar and Yogish Sabharwal and Sandeep Sen RANDOM EDGE can be exponential on abstract cubes Jiri Matousek and Tibor Szabo Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique Subhash Khot On the (Im)possibility of Cryptography with Imperfect Randomness Yevgeniy Dodis and Shien Jin Ong and Manoj Prabhakaran and Amit Sahai Constructing Expander Graphs by 2-lifts and Discrepancy vs. Spectral Gap Yonatan Bilu and Nathan Linial The Hardness of Metric Labeling Julia Chuzhoy and Joseph (Seffi) Naor Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game Rahul Savani and Bernhard von Stengel Maximum Matchings via Gaussian Elimination Marcin Mucha and Piotr Sankowski On the Integrality Ratio for Asymmetric TSP Moses Charikar and Michel X. Goemans and Howard Karloff Dynamic Transitive Closure via Dynamic Matrix Inverse Piotr Sankowski An edge in time saves nine: LP rounding approximation algorithms Anupam Gupta and R. Ravi and Amitabh Sinha Hardness of buy-at-bulk network design Matthew Andrews Edge pricing of multicommodity networks for heterogeneous selfish users George Karakostas and Stavros G. Kolliopoulos Multilinear-$NC_1$ $\ne$ Multilinear-$NC_2$ Ran Raz Dynamic approximate all-pairs shortest paths in undirected graphs Liam Roditty and Uri Zwick Triangulation and Embedding using Small Sets of Beacons Jon Kleinberg and Alex Slivkins and Tom Wexler Private codes or Succinct random codes that are (almost) perfect. Michael Langberg Edge-Disjoint Paths in Undirected Planar Graphs Chandra Chekuri and Sanjeev Khanna and F. Bruce Shepherd Worst-case to Average-case Reductions based on Gaussian Measures Daniele Micciancio and Oded Regev Algebras with Polynomial Identities and Computing the Determinant Steve Chien and Alistair Sinclair A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities Kamal Jain Quantum walk algorithm for element distinctness Andris Ambainis Approximating Edit Distance Efficiently Ziv Bar-Yossef and T.S. Jayram and Robert Krauthgamer and Ravi Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity Brian C. Dean and Michel X. Goemans and Jan Vondrak Testing Low-Degree Polynomials over Prime Fields Charanjit S. Jutla and Anindya C. Patthak and Atri Rudra and David Zuckerman An Unconditional Study of Computational Zero Knowledge Salil Vadhan Optimal Power-Down Strategies John Augustine and Sandy Irani and Chaitanya Swamy Deterministic extractors for bit-fixing sources by obtaining an independent seed Ariel Gabizon and Ran Raz and Ronen Shaltiel Cryptography in NC^0 Benny Applebaum and Yuval Ishai and Eyal Kushilevitz Stochastic Optimization is (almost) as easy as Deterministic Optimization David Shmoys and Chaitanya Swamy Learnability and Automatizability Misha Alekhnovich and Mark Braverman and Vitaly Feldman and Adam Klivans and Toni Pitassi The Price of Stability for Network Design with Fair Cost Allocation Elliot Anshelevich and Anirban Dasgupta and Jon Kleinberg and Eva Tardos and Tom Wexler and Tim Roughgarden Universally composable protocols with relaxed set-up assumptions Boaz Barak and Ran Canetti and Jesper Buus Nielsen Machine Minimization for Scheduling Jobs with Interval Constraints Julia Chuzhoy and Sudipto Guha and Sanjeev Khanna and Joseph On the List and Bounded Distance Decodibility of the Reed-Solomon Codes Qi Cheng and Daqing Wan Assignment-Testers: Towards a Combinatorial Proof of the PCP-Theorem Irit Dinur and Omer Reingold $O(\sqrt{\log n})$ approximation to SPARSEST CUT can be found in quadratic time Sanjeev Arora and Elad Hazan and Satyen Kale Adiabatic Quantum Computation is Equivalent to Standard Quantum Dorit Aharonov and Wim van Dam and Julia Kempe and Zeph Landau Extracting Randomness from Few Independent Sources Boaz Barak and Russell Impagliazzo and Avi Wigderson Spectral Analysis of Random Graphs with Skewed Degree Distributions Anirban Dasgupta and John E. Hopcroft and Frank McSherry Optimal Inapproximability Results for MAX-CUT and Other 2-variable CSPs? Subhash Khot and Guy Kindler and Elchanan Mossel and Ryan O'Donnell The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem Harold Connamacher and Michael Molloy On the Streaming Model Augmented with a Sorting Primitive Gagan Aggarwal and Mayur Datar and Sridhar Rajagopalan and Matthias Ruhl Dynamic Optimality--Almost Erik D. Demaine and Dion Harmon and John Iacono and Mihai Patrascu Taxes for heterogeneous selfish users in a multicommodity network Lisa Fleischer and Kamal Jain and Mohammad Mahdian Quantiziation of Classical Walk Based Algorithms Mario Szegedy