38. STOC 2006: Seattle, WA, USA

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 BibTeX

Session 1A

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

Session 1B

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

Session 2A

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

Session 2B

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

Session 3

Prabhakar Raghavan:
The changing face of web search: algorithms, auctions and advertising. 129
Electronic Edition (ACM DL) BibTeX

Session 4A

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

Session 4B

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

Session 5A

Moses Charikar, Konstantin Makarychev, Yury Makarychev:
Near-optimal algorithms for unique games. 205-214
Electronic Edition (ACM DL) BibTeX
Sanjeev Arora, Eden Chlamtac:
New approximation guarantee for chromatic number. 215-224
Electronic Edition (ACM DL) BibTeX

Session 5B

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

Session 6

Irit Dinur:
The PCP theorem by gap amplification. 241-250
Electronic Edition (ACM DL) BibTeX

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
Electronic Edition (ACM DL) BibTeX
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
Electronic Edition (ACM DL) BibTeX
Ittai Abraham, Yair Bartal, Ofer Neiman:
Advances in metric embedding theory. 271-286
Electronic Edition (ACM DL) BibTeX

Session 7B

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

Session 8A

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

Session 8B

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

Session 9

Russell Impagliazzo:
Can every randomized algorithm be derandomized? 373-374
Electronic Edition (ACM DL) BibTeX

Session 10A

Uriel Feige, Mohammad Mahdian:
Finding small balanced separators. 375-384
Electronic Edition (ACM DL) BibTeX
Rohit Khandekar, Satish Rao, Umesh V. Vazirani:
Graph partitioning using single commodity flows. 385-390
Electronic Edition (ACM DL) BibTeX
Jaroslav Nesetril, Patrice Ossona de Mendez:
Linear time low tree-width partitions and algorithmic consequences. 391-400
Electronic Edition (ACM DL) BibTeX
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
Electronic Edition (ACM DL) BibTeX

Session 10B

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

Session 11A

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

Session 11B

Peter DeMarzo, Ilan Kremer, Yishay Mansour:
Online trading algorithms and robust option pricing. 477-486
Electronic Edition (ACM DL) BibTeX
Konstantinos Panagiotou, Alexander Souza:
On adequate performance measures for paging. 487-496
Electronic Edition (ACM DL) BibTeX

Session 12

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

Session 13A

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

Session 13B

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

Session 14A

Dmitry Gavinsky, Julia Kempe, Oded Regev, Ronald de Wolf:
Bounded-error quantum state identification and exponential separations in communication complexity. 594-603
Electronic Edition (ACM DL) BibTeX
Sean Hallgren, Cristopher Moore, Martin Rötteler, Alexander Russell, Pranab Sen:
Limitations of quantum coset states for graph isomorphism. 604-617
Electronic Edition (ACM DL) BibTeX
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
Electronic Edition (ACM DL) BibTeX
Shengyu Zhang:
New upper and lower bounds for randomized and quantum local search. 634-643
Electronic Edition (ACM DL) BibTeX

Session 14B

Shahar Dobzinski, Noam Nisan, Michael Schapira:
Truthful randomized mechanisms for combinatorial auctions. 644-652
Electronic Edition (ACM DL) BibTeX
Simon Fischer, Harald Räcke, Berthold Vöcking:
Fast convergence to Wardrop equilibria by adaptive sampling methods. 653-662
Electronic Edition (ACM DL) BibTeX
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
Electronic Edition (ACM DL) BibTeX

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
Electronic Edition (ACM DL) BibTeX
David Zuckerman:
Linear degree extractors and the inapproximability of max clique and chromatic number. 681-690
Electronic Edition (ACM DL) BibTeX
Jesse Kamp, Anup Rao, Salil P. Vadhan, David Zuckerman:
Deterministic extractors for small-space sources. 691-700
Electronic Edition (ACM DL) BibTeX
Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz:
On basing one-way functions on NP-hardness. 701-710
Electronic Edition (ACM DL) BibTeX
Bella Dubrov, Yuval Ishai:
On the randomness complexity of efficient sampling. 711-720
Electronic Edition (ACM DL) BibTeX

Session 15B

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