• 
  Harold N. Gabow, Ronald Fagin (Eds.): Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005. ACM 2005 ISBN 1-58113-960-8

Session 1A

• 
  Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson: Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. 1-10
• 
  Ran Raz: Extractors with weak random seeds. 11-20
• 
  Andrej Bogdanov: Pseudorandom generators for low degree polynomials. 21-30
• 
  Luca Trevisan: On uniform amplification of hardness in NP. 31-38

Session 1B

• 
  Patrick Briest, Piotr Krysta, Berthold Vöcking: Approximation techniques for utilitarian mechanism design. 39-48
• 
  Christos H. Papadimitriou: Computing correlated equilibria in multi-player games. 49-56
• 
  Baruch Awerbuch, Yossi Azar, Amir Epstein: Large the price of routing unsplittable flow. 57-66
• 
  George Christodoulou, Elias Koutsoupias: The price of anarchy of finite congestion games. 67-73
• 
  Bruno Codenotti, Benton McCune, Kasturi R. Varadarajan: Market equilibrium via the excess demand function. 74-83

Session 2A

• 
  Oded Regev: On lattices, learning with errors, random linear codes, and cryptography. 84-93
• 
  Miklós Ajtai: Representing hard lattices with O(n log n) bits. 94-103

Session 2B

• 
  Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu: On dynamic range reporting in one dimension. 104-111
• 
  Mikkel Thorup: Worst-case update times for fully-dynamic all-pairs shortest paths. 112-119

Keynote

• 
  Lance Fortnow: Beyond NP: the work and legacy of Larry Stockmeyer. 120-127

Session 4A

• 
  Noga Alon, Asaf Shapira: Every monotone graph property is testable. 128-137
• 
  Eldar Fischer, Ilan Newman: Testing versus estimation of graph properties. 138-146
• 
  Ronitt Rubinfeld, Rocco A. Servedio: Testing monotone high-dimensional distributions. 147-156
• 
  Katalin Friedl, Gábor Ivanyos, Miklos Santha: Efficient testing of groups. 157-166

Session 4B

• 
  Joseph Cheriyan, Adrian Vetta: Approximation algorithms for network design with metric costs. 167-175
• 
  Moses Charikar, Adriana Karagiozova: On non-uniform multicommodity buy-at-bulk network design. 176-182
• 
  Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: Multicommodity flow, well-linked terminals, and routing problems. 183-192
• 
  Mohammad Taghi Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Räcke: Oblivious routing in directed graphs with random demands. 193-201

Session 5A

• 
  Piotr Indyk, David P. Woodruff: Optimal approximations of the frequency moments of data streams. 202-208
• 
  Gereon Frahling, Christian Sohler: Coresets in dynamic geometric data streams. 209-217
• 
  Rafail Ostrovsky, Yuval Rabani: Low distortion embeddings for edit distance. 218-224
• 
  Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos: Low-distortion embeddings of general metrics into the line. 225-233

Session 5B

• 
  Mikolaj Bojanczyk, Thomas Colcombet: Tree-walking automata do not recognize all regular languages. 234-243
• 
  Itai Benjamini, Oded Schramm, David Bruce Wilson: Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read. 244-250
• 
  Michael Alekhnovich: Lower bounds for k-DNF resolution on random 3-CNFs. 251-256
• 
  Michal Koucký, Pavel Pudlák, Denis Thérien: Bounded-depth circuits: separating wires from gates. 257-265

Session 6A

• 
  Eli Ben-Sasson, Madhu Sudan: Simple PCPs with poly-log rate and query complexity. 266-275
• 
  Matthew Andrews, Lisa Zhang: Hardness of the undirected edge-disjoint paths problem. 276-283
• 
  Matthew Andrews, Lisa Zhang: Hardness of the undirected congestion minimization problem. 284-293
• 
  Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis: Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. 294-303

Session 6B

• 
  Saugata Basu, Richard Pollack, Marie-Françoise Roy: Computing the first Betti number and the connected components of semi-algebraic sets. 304-312
• 
  Saugata Basu: Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities. 313-322
• 
  Xi Chen, Xiaotie Deng: On algorithms for discrete and approximate brouwer fixed points. 323-330
• 
  Yossi Azar, Amir Epstein: Convex programming for scheduling unrelated parallel machines. 331-337

Session 7A

• 
  Saurabh Sanghvi, Salil P. Vadhan: The round complexity of two-party random selection. 338-347
• 
  Lance Fortnow, Rahul Santhanam, Luca Trevisan: Hierarchies for semantic classes. 348-355

Session 7B

• 
  Haim Kaplan, Eyal Kushilevitz, Yishay Mansour: Learning with attribute costs. 356-365
• 
  Elchanan Mossel, Sébastien Roch: Learning nonsingular phylogenies and hidden Markov models. 366-375

Best Paper

• 
  Omer Reingold: Undirected ST-connectivity in log-space. 376-385

Session 9A

• 
  Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, Ravi Sundaram: Universal approximations for TSP, Steiner tree, and set cover. 386-395
• 
  Naveen Garg: Saving an epsilon: a 2-approximation for the k-MST problem in graphs. 396-402
• 
  Ben Morris: The mixing time of the Thorp shuffle. 403-412
• 
  Mary Cryan, Martin E. Dyer, Dana Randall: Approximately counting integral flows and cell-bounded contingency tables. 413-422

Session 9B

• 
  Van H. Vu: Spectral norm of random matrices. 423-430
• 
  Terence Tao, Van H. Vu: On random pm 1 matrices: singularity and determinant. 431-440
• 
  Abraham Flaxman, Alan M. Frieze, Juan Carlos Vera: On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem. 441-449
• 
  Micah Adler, Jeff Edmonds, Jirí Matousek: Towards asymptotic optimality in probabilistic packet marking. 450-459

Session 10A

• 
  Yaoyun Shi: Tensor norms and the classical communication complexity of nonlocal quantum measurement. 460-467
• 
  Sean Hallgren: Fast quantum algorithms for computing the unit group and class group of a number field. 468-474
• 
  Arthur Schmidt, Ulrich Vollmer: Polynomial time quantum algorithm for the computation of the unit group of a number field. 475-480
• 
  Michael Ben-Or, Avinatan Hassidim: Fast quantum byzantine agreement. 481-485

Session 10B

• 
  Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor: Quadratic forms on graphs. 486-493
• 
  Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng: Lower-stretch spanning trees. 494-503
• 
  Daniel Gonçalves: Edge partition of planar sraphs into two outerplanar graphs. 504-512

Session 11A

• 
  Luis von Ahn, Nicholas J. Hopper, John Langford: Covert two-party computation. 513-522
• 
  Hoeteck Wee: On obfuscating point functions. 523-532
• 
  Rafael Pass, Alon Rosen: New and improved constructions of non-malleable cryptographic protocols. 533-542
• 
  Matt Lepinski, Silvio Micali, Abhi Shelat: Collusion-free protocols. 543-552

Session 11B

• 
  Sanjeev Arora, James R. Lee, Assaf Naor: Euclidean distortion and the sparsest cut. 553-562
• 
  Uriel Feige, Mohammad Taghi Hajiaghayi, James R. Lee: Improved approximation algorithms for minimum-weight vertex separators. 563-572
• 
  Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev: O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. 573-581
• 
  Joseph Naor, Roy Schwartz: Balanced metric labeling. 582-591

Session 12A

• 
  Zeev Dvir, Amir Shpilka: Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. 592-601
• 
  Venkatesan Guruswami, Atri Rudra: Limits to list decoding Reed-Solomon codes. 602-609

Session 12B

• 
  Shahar Dobzinski, Noam Nisan, Michael Schapira: Approximation algorithms for combinatorial auctions with complement-free bidders. 610-618
• 
  Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan: Derandomization of auctions. 619-625

Best Student Paper

• 
  Vladimir Trifonov: An O(log n log log n) space algorithm for undirected st-connectivity. 626-633

Session 14A

• 
  Scott Aaronson: The complexity of agreement. 634-643
• 
  Yael Tauman Kalai, Yehuda Lindell, Manoj Prabhakaran: Concurrent general composition of secure protocols in the timing model. 644-653
• 
  Yevgeniy Dodis, Adam Smith: Correcting errors without leaking partial information. 654-663
• 
  Thomas Holenstein: Key agreement from weak bit agreement. 664-673

Session 14B

• 
  Ferdinando Cicalese, Eduardo Sany Laber: A new strategy for querying priced information. 674-683
• 
  Nir Ailon, Moses Charikar, Alantha Newman: Aggregating inconsistent information: ranking and clustering. 684-693
• 
  Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore: On the bias of traceroute sampling: or, power-law degree distributions in regular graphs. 694-703
• 
  Christian Scheideler: How to spread adversarial nodes?: rotate! 704-713

Session 15A

• 
  Eli Gafni, Rachid Guerraoui, Bastian Pochon: From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement. 714-722
• 
  Prasad Jayanti: An optimal multi-writer snapshot algorithm. 723-732
• 
  Bogdan S. Chlebus, Dariusz R. Kowalski: Cooperative asynchronous update of shared memory. 733-739

Session 15B

• 
  Johan Håstad: Every 2-CSP allows nontrivial approximation. 740-746
• 
  Wenceslas Fernandez de la Vega, Marek Karpinski, Ravi Kannan, Santosh Vempala: Tensor decomposition and approximation schemes for constraint satisfaction problems. 747-754
• 
  Klaus Jansen, Rob van Stee: On strip packing With rotations. 755-761