List of accepted papers for STOC 2005: Quadratic forms on graphs Noga Alon, Konstantin Makarychev, Yuri Makarychev, Assaf Naor Representing Hard Lattices with O(n log n) Bits Miklos Ajtai Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits Zeev Dvir, Amir Shpilka Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read Itai Benjamini, Oded Schramm, David B. Wilson Worst-case update times for fully-dynamic all-pairs shortest paths Mikkel Thorup Every Monotone Graph Property is Testable Noga Alon, Asaf Shapira On Dynamic Range Reporting in One Dimension Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu Every 2-CSP allows nontrivial approximation Johan Hastad Computing the first Betti number and the connected components of semi-algebraic sets. Saugata Basu, Richard Pollack, Marie-Francoise Roy Polynomial Time Algorithm for Computing the Top Betti Numbers of Semi-algebraic Sets Saugata Basu Extractors with Weak Random Seeds Ran Raz On Algorithms for Discrete and Approximate Brouwer Fixed Points Xi Chen, Xiaotie Deng Spectral norm of random matrices V. Vu On random $\pm 1$ matrices: Singularity and Determinant T. Tao, V. Vu. Testing versus Estimation of Graph Properties Eldar Fischer, Ilan Newman Euclidean distortion and the Sparsest Cut Sanjeev Arora, James R. Lee, Assaf Naor On Lattices, Learning with Errors, Random Linear Codes, and Cryptography Oded Regev Approximately counting integral flows and cell-bounded contingency tables Mary Cryan, Martin Dyer, Dana Randall Key Agreement from Weak Bit Agreement Thomas Holenstein Undirected ST-Connectivity in Log-Space Omer Reingold How to Spread Adversarial Nodes? Rotate! Christian Scheideler Simple PCPs with Poly-log Rate and Query Complexity Eli Ben-Sasson, Madhu Sudan A New Strategy for Querying Priced Information Ferdinando Cicalese, Eduardo Sany Laber On the average case performance of some facility location heuristics Abraham D. Flaxman, Alan M. Frieze, Juan C. Vera Efficient testing of groups Katalin Friedl, Gabor Ivanyos, Miklos Santha Improved approximation algorithms for minimum-weight vertex separators Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee Bounded-depth circuits: separating wires from gates. Michal Koucky, Pavel Pudlak, Denis Therien Approximation Algorithms for Network Design with Metric Costs. Joseph Cheriyan, Adrian Vetta On Uniform Amplification of Hardness in NP Luca Trevisan Computing Correlated Equilibria in Multiplayer Games (Extended Christos H. Papadimitriou A O(log n log log n) Space Algorithm for Undirected Connectivity Vladimir Trifonov Lower-Stretch Spanning Trees Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng Cooperative Asynchronous Update of Shared Memory Bogdan Chlebus, Dariusz Kowalski Collusion-free protocols Matt Lepinksi, Silvio Micali, abhi shelat Optimal Approximations of the Frequency Moments Piotr Indyk, David Woodruff Multicommodity flow, well-linked terminals, and routing problems Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd Limits to List Decoding Reed-Solomon Codes Venkatesan Guruswami, Atri Rudra Low-Distortion EMbeddings of General Metrics Into the Line Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos Lower bounds for $k$-DNF Resolution on random 3-CNFs Michael Alekhnovich Low Distortion Embeddings for Edit Distance Rafail Ostrovsky, Yuval Rabani On the mixing time for the Thorp shuffle Ben Morris Edge partition of planar graphs into two outerplanar graphs. Goncalves daniel Saving an $e$: A 2-approximation for the $k$-MST problem in graphs. Naveen Garg The Price of Routing Unsplittable Flow B. Awerbuch, Y. Azar, A. Epstein Convex Programming for Scheduling Unrelated Parallel Machines Y. Azar, A. Epstein Learning Nonsingular Phylogenies and Hidden Markov Models Elchanan Mossel, Sebastien Roch On Strip Packing With Rotations Klaus Jansen, Rob van Stee Concurrent General Composition of Secure Protocols in the Timing Model Yael Kalai, Yehuda Lindell, Manoj Prabhakaran Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field Sean Hallgren Tensor Decomposition and Approximation Schemes for CSP W.F.dela Vega, R. Kannan, M. Karpinski, S. Vempala Approximation Techniques for Utilitarian Mechanism Design Patrick Briest, Piotr Krysta, Berthold Voecking Balanced Metric Labeling Joseph (Seffi) Naor, Roy Schwartz Learning with Attribute Costs Haim Kaplan, Eyal Kushilevitz, Yishay Mansour Market Equilibrium via the Excess Demand Function Bruno Codenotti, Benton McCune, Kasturi Varadarajan Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders Shahar Dobzinski, Noam Nisan, Michael Schapira Testing Monotone High-Dimensional Distributions Ronitt Rubinfeld, Rocco A. Servedio The Complexity of Agreement Scott Aaronson Aggregating Inconsistent Information: Ranking and Clustering Nir Ailon, Moses Charikar, Alantha Newman Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson O(\sqrt{log n}) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems. Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev Fast Quantum Byzantine Agreement Michael Ben-Or, Avinatan Hassidim Pseudorandom generators for low degree polynomials Andrej Bogdanov From a Static Impossibility to an Adaptive Lower Bound: The Complexity of Early Deciding Set Agreement Eli Gafni, Rachid Guerraoui, Bastian Pochon On Non-uniform Multicommodity Buy-at-Bulk Network Design Moses Charikar, Adriana Karagiozova Promise Hierarchies Lance Fortnow, Rahul Santhanam, Luca Trevisan Hardness of the Undirected Edge-Disjoint Paths Problem Matthew Andrews, Lisa Zhang Hardness of the Undirected Congestion Minimization Problem Matthew Andrews, Lisa Zhang Universal Approximations for TSP, Steiner Tree and Set Cover Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, Ravi Sundaram On Obfuscating Point Functions Hoeteck Wee Coresets in dynamic geometric data streams Gereon Frahling, Christian Sohler Tensor norms and the classical communication complexity of nonlocal quantum measurement Yaoyun Shi Oblivious Routing in Directed Graphs with Random Demands Mohammad T. Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Raecke The price of anarchy of finite congestion games George Christodoulou, Elias Koutsoupias Covert Two-Party Computation Luis von Ahn, Nicholas J. Hopper, John Langford New and Improved Constructions of Non-Malleable Cryptographic Protocols Rafael Pass, Alon Rosen Towards Asymptotic Optimality in Probabilistic Packet Marking Micah Adler, Jeff Edmonds, Jiri Matousek Polynomial Time Quantum Algorithm for the Computation of the Unit Group of a Number Field Arthur Schmidt, Ulrich Vollmer Derandomization of Auctions Gagan Aggarwal, Amos Fiat, Andrew Goldberg, Jason Hartline, Nicole Immorlica, Madhu Sudan An Optimal Multi-Writer Snapshot Algorithm Prasad Jayanti Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis The Round Complexity of Two-Party Random Selection Saurabh Sanghvi, Salil Vadhan Tree-Walking Automata Do Not Recognize All Regular Languages Mikolaj Bojanczyk, Thomas Colcombet On the Bias of Traceroute Sampling, or: Why almost every network looks like it has a power law Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore Correcting Errors Without Leaking Partial Information Yevgeniy Dodis, Adam Smith