default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID38th STOC 2006: Seattle, WA, USA
- Jon M. Kleinberg:
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 n3-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 M. 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-12-12 22:52 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
