• 
  László Babai (Ed.): Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004. ACM 2004 ISBN 1-58113-852-0

Session 1A

• 
  Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan: Robust pcps of proximity, shorter pcps and applications to coding. 1-10
• 
  Jonas Holmerin, Subhash Khot: A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. 11-20
• 
  Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor: Asymmetric k-center is log^* n-hard to approximate. 21-27
• 
  Julia Chuzhoy, Joseph Naor: New hardness results for congestion minimization and machine scheduling. 28-34
• 
  Susanne Albers, Markus Schmidt: On the performance of greedy algorithms in packet buffering. 35-44

Session 1B

• 
  Baruch Awerbuch, Robert D. Kleinberg: Adaptive routing with end-to-end feedback: distributed learning and geometric approaches. 45-53
• 
  Gurmeet Singh Manku, Moni Naor, Udi Wieder: Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks. 54-63
• 
  Yossi Azar, Yossi Richter: The zero-one principle for switching networks. 64-71

Session 2A

• 
  Noga Alon, Assaf Naor: Approximating the cut-norm via Grothendieck's inequality. 72-80
• 
  Daniel A. Spielman, Shang-Hua Teng: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. 81-90

Session 2B

• 
  Richard Cole, Lee-Ad Gottlieb, Moshe Lewenstein: Dictionary matching and indexing with errors and don't cares. 91-100
• 
  Irene Finocchi, Giuseppe F. Italiano: Sorting and searching in the presence of memory faults (without redundancy). 101-110
• 
  Andris Ambainis: Quantum algorithms a decade after shor. 111

Session 4A

• 
  Andrew Chi-Chih Yao: Graph entropy and quantum sorting problems. 112-117
• 
  Scott Aaronson: Multilinear formulas and skepticism of quantum computing. 118-127
• 
  Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis: Exponential separation of quantum and classical one-way communication complexity. 128-137

Session 4B

• 
  Guy Kortsarz, Zeev Nutov: Approximation algorithm for k-node connected subgraphs via critical graphs. 138-145
• 
  Daniel Bienstock, Garud Iyengar: Solving fractional packing problems in O^ast(1/?) iterations. 146-155
• 
  Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: The all-or-nothing multicommodity flow problem. 156-165

Session 5A

• 
  Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson: Approximation algorithms for deadline-TSP and vehicle routing with time-windows. 166-174
• 
  Artur Czumaj, Christian Sohler: Estimating the weight of metric minimum spanning trees in sublinear-time. 175-183
• 
  Liam Roditty, Uri Zwick: A fully dynamic reachability algorithm for directed graphs with an almost linear update time. 184-191

Session 5B

• 
  Alexander Healy, Salil P. Vadhan, Emanuele Viola: Using nondeterminism to amplify hardness. 192-201
• 
  Rajeev Alur, P. Madhusudan: Visibly pushdown languages. 202-211
• 
  Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia: Linear FPT reductions and computational lower bounds. 212-221
• 
  Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. 222-231

Session 7A

• 
  Rafael Pass: Bounded-concurrent secure multi-party computation with a dishonest majority. 232-241
• 
  Manoj Prabhakaran, Amit Sahai: New notions of security: achieving universal composability without trusted setup. 242-251
• 
  Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen: Completeness in two-party secure computation: a computational view. 252-261
• 
  Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai: Batch codes and their applications. 262-271

Session 7B

• 
  Claire Kenyon, Yuval Rabani, Alistair Sinclair: Low distortion maps between point sets. 272-280
• 
  Kunal Talwar: Bypassing the embedding: algorithms for low dimensional metrics. 281-290
• 
  Sariel Har-Peled, Soham Mazumdar: On coresets for k-means and k-median clustering. 291-300
• 
  Jean-Daniel Boissonnat, David Cohen-Steiner, Gert Vegter: Isotopic implicit surface meshing. 301-309

Session 8A

• 
  László Lovász, Santosh Vempala: Hit-and-run from a corner. 310-314
• 
  John Dunagan, Santosh Vempala: A simple polynomial-time rescaling algorithm for solving linear programs. 315-320

Session 8B

• 
  Bogdan S. Chlebus, Dariusz R. Kowalski, Alexander A. Shvartsman: Collective asynchronous reading with polylogarithmic worst-case overhead. 321-330
• 
  Michael Elkin: Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. 331-340
• 
  Éva Tardos: Network games. 341-342

Session 10A

• 
  René Beier, Berthold Vöcking: Typical properties of winners and losers in discrete optimization. 343-352
• 
  Retsef Levi, Robin Roundy, David B. Shmoys: Primal-dual algorithms for deterministic inventory problems. 353-362
• 
  Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar: Multi-processor scheduling to minimize flow time with epsilon resource augmentation. 363-372

Session 10B

• 
  Piotr Indyk: Algorithms for dynamic geometric problems over data streams. 373-380
• 
  Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld: Sublinear algorithms for testing monotone and unimodal distributions. 381-390
• 
  Eldar Fischer: The difficulty of testing for isomorphism against a graph that is given in advance. 391-397

Session 11A

• 
  José R. Correa, Michel X. Goemans: An approximate König's theorem for edge-coloring weighted bipartite graphs. 398-406
• 
  Harold N. Gabow: Finding paths and cycles of superpolylogarithmic length. 407-416
• 
  Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha: Boosted sampling: approximation algorithms for stochastic optimization. 417-426

Session 11B

• 
  Amir Shpilka, Avi Wigderson: Derandomizing homomorphism testing in general groups. 427-435
• 
  Venkatesan Guruswami: Better extractors for better codes? 436-444
• 
  Eyal Rozenman, Aner Shalev, Avi Wigderson: A new family of Cayley expanders (?). 445-454
• 
  Jonathan A. Kelner: Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. 455-464
• 
  Scott Aaronson: Lower bounds for local search by quantum arguments. 465-474
• 
  Peter Bürgisser, Felipe Cucker: Counting complexity classes for numeric computations II: algebraic and semialgebraic sets. 475-485

Session 14A

• 
  Miklós Ajtai: A conjecture about polynomial time computable lattice-lattice functions. 486-493
• 
  Miklos Santha, Mario Szegedy: Quantum and classical query complexities of local search are polynomially related. 494-501
• 
  Ben Reichardt: The quantum adiabatic optimization algorithm and local minima. 502-510
• 
  Rahul Garg, Sanjiv Kapoor: Auction algorithms for market equilibrium. 511-518

Session 14B

• 
  Nikhil R. Devanur: The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results. 519-528
• 
  Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta: (Almost) tight bounds and existence theorems for confluent flows. 529-538
• 
  Kenji Obata: Approximate max-integral-flow/min-multicut theorems. 539-545

Session 15A

• 
  Mihai Patrascu, Erik D. Demaine: Lower bounds for dynamic connectivity. 546-553
• 
  Nir Ailon, Bernard Chazelle: Lower bounds for linear degeneracy testing. 554-560

Session 15B

• 
  David Kempe, Frank McSherry: A decentralized algorithm for spectral analysis. 561-568
• 
  Jon M. Kleinberg, Mark Sandler: Using mixture models for collaborative filtering. 569-578
• 
  Avi Wigderson: Depth through breadth, or why should we attend talks in other areas? 579

Session 17A

• 
  Ashish Goel, Sanatan Rai, Bhaskar Krishnamachari: Sharp thresholds For monotone properties in random geometric graphs. 580-586
• 
  Dimitris Achlioptas, Assaf Naor: The two possible values of the chromatic number of a random graph. 587-593
• 
  Uriel Feige: On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. 594-603
• 
  Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar: The complexity of pure Nash equilibria. 604-612

Session 17B

• 
  Martin Gairing, Thomas Lücking, Marios Mavronicolas, Burkhard Monien: Computing Nash equilibria for scheduling on restricted parallel links. 613-622
• 
  Joseph Y. Halpern, Vanessa Teague: Rational secret sharing and multiparty computation: extended abstract. 623-632
• 
  Ran Raz: Multi-linear formulas for permanent and determinant are of super-polynomial size. 633-641