• 
  Jon M. Kleinberg (Ed.): Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006. ACM 2006 ISBN 1-59593-134-1

Session 1A

• 
  Venkatesan Guruswami, Atri Rudra: Explicit capacity-achieving list-decodable codes. 1-10
• 
  Alex Samorodnitsky, Luca Trevisan: Gowers uniformity, influence of variables, and PCPs. 11-20
• 
  Dana Moshkovitz, Ran Raz: Sub-constant error low degree test of almost-linear size. 21-30

Session 1B

• 
  Nikhil Bansal, Maxim Sviridenko: The Santa Claus problem. 31-40
• 
  Uriel Feige: On maximizing welfare when utility functions are subadditive. 41-50
• 
  Jonathan A. Kelner, Daniel A. Spielman: A randomized polynomial-time simplex algorithm for linear programming. 51-60

Session 2A

• 
  Paul W. Goldberg, Christos H. Papadimitriou: Reducibility among equilibrium problems. 61-70
• 
  Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou: The complexity of computing a Nash equilibrium. 71-78
• 
  Tim Roughgarden, Mukund Sundararajan: New trade-offs in cost-sharing mechanisms. 79-88
• 
  Ara Hayrapetyan, Éva Tardos, Tom Wexler: The effect of collusion in congestion games. 89-98

Session 2B

• 
  Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell, Erez Petrank: Black-box constructions for secure computation. 99-108
• 
  Eyal Kushilevitz, Yehuda Lindell, Tal Rabin: Information-theoretically secure protocols and security under composition. 109-118
• 
  Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb: Private approximation of search problems. 119-128

Session 3

• 
  Prabhakar Raghavan: The changing face of web search: algorithms, auctions and advertising. 129

Session 4A

• 
  Dimitris Achlioptas, Federico Ricci-Tersenghi: On the solution-space geometry of random constraint satisfaction problems. 130-139
• 
  Dror Weitz: Counting independent sets up to the tree threshold. 140-149
• 
  Mario Szegedy: The DLT priority sampling is essentially optimal. 150-158
• 
  Constantinos Daskalakis, Elchanan Mossel, Sébastien Roch: Optimal phylogenetic reconstruction. 159-168

Session 4B

• 
  Panagiota Fatourou, Faith Ellen Fich, Eric Ruppert: Time-space tradeoffs for implementations of snapshots. 169-178
• 
  Michael Ben-Or, Elan Pavlov, Vinod Vaikuntanathan: Byzantine agreement in the full-information model in O(log n) rounds. 179-186
• 
  Spyridon Antonakopoulos: Fast leader-election protocols with bounded cheaters' edge. 187-196
• 
  Sung-woo Cho, Ashish Goel: Pricing for fairness: distributed resource allocation for multiple objectives. 197-204

Session 5A

• 
  Moses Charikar, Konstantin Makarychev, Yury Makarychev: Near-optimal algorithms for unique games. 205-214
• 
  Sanjeev Arora, Eden Chlamtac: New approximation guarantee for chromatic number. 215-224

Session 5B

• 
  Virginia Vassilevska, Ryan Williams: Finding a maximum weight triangle in n^3-Delta time, with applications. 225-231
• 
  Mihai Patrascu, Mikkel Thorup: Time-space trade-offs for predecessor search. 232-240

Session 6

• 
  Irit Dinur: The PCP theorem by gap amplification. 241-250

Session 7A

• 
  Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira: A combinatorial characterization of the testable graph properties: it's all about regularity. 251-260
• 
  Christian Borgs, Jennifer T. Chayes, László Lovász, Vera T. Sós, Balázs Szegedy, Katalin Vesztergombi: Graph limits and parameter testing. 261-270
• 
  Ittai Abraham, Yair Bartal, Ofer Neiman: Advances in metric embedding theory. 271-286

Session 7B

• 
  Minh-Huyen Nguyen, Salil P. Vadhan: Zero knowledge with efficient provers. 287-295
• 
  John Watrous: Zero-knowledge against quantum attacks. 296-305
• 
  Silvio Micali, Rafael Pass: Local zero knowledge. 306-315

Session 8A

• 
  Jan Remy, Angelika Steger: A quasi-polynomial time approximation scheme for minimum weight triangulation. 316-325
• 
  Kenneth L. Clarkson: Building triangulations using epsilon-nets. 326-335
• 
  Tetsuo Asano, Jirí Matousek, Takeshi Tokuyama: The distance trisector curve. 336-343

Session 8B

• 
  Irit Dinur, Elchanan Mossel, Oded Regev: Conditional hardness for approximate coloring. 344-353
• 
  Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider: Clique-width minimization is NP-hard. 354-362
• 
  Vitaly Feldman: Hardness of approximate two-level logic minimization and PAC learning with membership queries. 363-372

Session 9

• 
  Russell Impagliazzo: Can every randomized algorithm be derandomized? 373-374

Session 10A

• 
  Uriel Feige, Mohammad Mahdian: Finding small balanced separators. 375-384
• 
  Rohit Khandekar, Satish Rao, Umesh V. Vazirani: Graph partitioning using single commodity flows. 385-390
• 
  Jaroslav Nesetril, Patrice Ossona de Mendez: Linear time low tree-width partitions and algorithmic consequences. 391-400
• 
  Ken-ichi Kawarabayashi, Bojan Mohar: Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs. 401-416

Session 10B

• 
  Leonid Gurvits: Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications. 417-426
• 
  Dorit Aharonov, Vaughan Jones, Zeph Landau: A polynomial quantum algorithm for approximating the Jones polynomial. 427-436
• 
  Irit Dinur, Ehud Friedgut, Guy Kindler, Ryan O'Donnell: On the fourier tails of bounded functions over the discrete cube. 437-446
• 
  Oded Regev, Ricky Rosen: Lattice problems and norm embeddings. 447-456

Session 11A

• 
  Omer Reingold, Luca Trevisan, Salil P. Vadhan: Pseudorandom walks on regular digraphs and the RL vs. L problem. 457-466
• 
  Wojciech Plandowski: An efficient algorithm for solving word equations. 467-476

Session 11B

• 
  Peter DeMarzo, Ilan Kremer, Yishay Mansour: Online trading algorithms and robust option pricing. 477-486
• 
  Konstantinos Panagiotou, Alexander Souza: On adequate performance measures for paging. 487-496

Session 12

• 
  Anup Rao: Extractors for a constant number of polynomially small min-entropy independent sources. 497-506
• 
  Jakob Nordström: Narrow proofs may be spacious: separating space and width in resolution. 507-516

Session 13A

• 
  Matthew Andrews, Lisa Zhang: Logarithmic hardness of the directed congestion minimization problem. 517-526
• 
  Julia Chuzhoy, Sanjeev Khanna: Hardness of cut problems in directed graphs. 527-536
• 
  Nikhil R. Devanur, Subhash Khot, Rishi Saket, Nisheeth K. Vishnoi: Integrality gaps for sparsest cut and minimum linear arrangement problems. 537-546
• 
  Howard J. Karloff, Subhash Khot, Aranyak Mehta, Yuval Rabani: On earthmover distance, metric labeling, and 0-extension. 547-556

Session 13B

• 
  Nir Ailon, Bernard Chazelle: Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. 557-563
• 
  Sunil Arya, Theocharis Malamatos, David M. Mount: On the importance of idempotence. 564-573
• 
  Richard Cole, Lee-Ad Gottlieb: Searching dynamic point sets in spaces with bounded doubling dimension. 574-583
• 
  Dana Angluin, James Aspnes, Jiang Chen, Yinghua Wu: Learning a circuit by injecting values. 584-593

Session 14A

• 
  Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf: Bounded-error quantum state identification and exponential separations in communication complexity. 594-603
• 
  Sean Hallgren, Cristopher Moore, Martin Rötteler, Alexander Russell, Pranab Sen: Limitations of quantum coset states for graph isomorphism. 604-617
• 
  Andris Ambainis, Robert Spalek, Ronald de Wolf: A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs. 618-633
• 
  Shengyu Zhang: New upper and lower bounds for randomized and quantum local search. 634-643

Session 14B

• 
  Shahar Dobzinski, Noam Nisan, Michael Schapira: Truthful randomized mechanisms for combinatorial auctions. 644-652
• 
  Simon Fischer, Harald Räcke, Berthold Vöcking: Fast convergence to Wardrop equilibria by adaptive sampling methods. 653-662
• 
  Lisa Fleischer, Jochen Könemann, Stefano Leonardi, Guido Schäfer: Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree. 663-670

Session 15A

• 
  Boaz Barak, Anup Rao, Ronen Shaltiel, Avi Wigderson: 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. 671-680
• 
  David Zuckerman: Linear degree extractors and the inapproximability of max clique and chromatic number. 681-690
• 
  Jesse Kamp, Anup Rao, Salil P. Vadhan, David Zuckerman: Deterministic extractors for small-space sources. 691-700
• 
  Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz: On basing one-way functions on NP-hardness. 701-710
• 
  Bella Dubrov, Yuval Ishai: On the randomness complexity of efficient sampling. 711-720

Session 15B

• 
  Nikhil Bansal, Amit Chakrabarti, Amir Epstein, Baruch Schieber: A quasi-PTAS for unsplittable flow on line graphs. 721-729
• 
  Naveen Garg, Amit Kumar: Minimizing average flow time on related machines. 730-738
• 
  Retsef Levi, Robin Roundy, David B. Shmoys: Provably near-optimal sampling-based algorithms for Stochastic inventory control models. 739-748
• 
  Philip N. Klein: A subset spanner for Planar graphs, : with application to subset TSP. 749-756
• 
  Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd: Edge-disjoint paths in Planar graphs with constant congestion. 757-766