Proceedings of the 38th Annual ACM Symposium on Theory of Computing
BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
EDIT!
CC-BY
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter

Jon M. Kleinberg
Proceedings of the 38th Annual ACM Symposium on Theory of Computing
STOC, 2006.

TCS
DBLP
Scholar
Full names Links ISxN
@proceedings{STOC-2006,
	address       = "Seattle, Washington, USA",
	editor        = "Jon M. Kleinberg",
	isbn          = "1-59593-134-1",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 38th Annual ACM Symposium on Theory of Computing}",
	year          = 2006,
}

Contents (79 items)

STOC-2006-GuruswamiR
Explicit capacity-achieving list-decodable codes (VG, AR), pp. 1–10.
STOC-2006-SamorodnitskyT
Gowers uniformity, influence of variables, and PCPs (AS, LT), pp. 11–20.
STOC-2006-MoshkovitzR #fault
Sub-constant error low degree test of almost-linear size (DM, RR), pp. 21–30.
STOC-2006-BansalS #problem
The Santa Claus problem (NB, MS), pp. 31–40.
STOC-2006-Feige #on the
On maximizing welfare when utility functions are subadditive (UF), pp. 41–50.
STOC-2006-KelnerS #algorithm #linear #polynomial #programming #random
A randomized polynomial-time simplex algorithm for linear programming (JAK, DAS), pp. 51–60.
STOC-2006-GoldbergP #equilibrium #problem
Reducibility among equilibrium problems (PWG, CHP), pp. 61–70.
STOC-2006-DaskalakisGP #complexity #equilibrium #nash
The complexity of computing a Nash equilibrium (CD, PWG, CHP), pp. 71–78.
STOC-2006-RoughgardenS #trade-off
New trade-offs in cost-sharing mechanisms (TR, MS), pp. 79–88.
STOC-2006-HayrapetyanTW #game studies
The effect of collusion in congestion games (AH, ÉT, TW), pp. 89–98.
STOC-2006-IshaiKLP #black box
Black-box constructions for secure computation (YI, EK, YL, EP), pp. 99–108.
STOC-2006-KushilevitzLR #composition #protocol #security
Information-theoretically secure protocols and security under composition (EK, YL, TR), pp. 109–118.
STOC-2006-BeimelCNW #approximate #problem
Private approximation of search problems (AB, PC, KN, EW), pp. 119–128.
STOC-2006-Raghavan #algorithm #web
The changing face of web search: algorithms, auctions and advertising (PR), p. 129.
STOC-2006-AchlioptasR #constraints #geometry #on the #problem #random
On the solution-space geometry of random constraint satisfaction problems (DA, FRT), pp. 130–139.
STOC-2006-Weitz #independence #set
Counting independent sets up to the tree threshold (DW), pp. 140–149.
STOC-2006-Szegedy
The DLT priority sampling is essentially optimal (MS), pp. 150–158.
STOC-2006-DaskalakisMR #re-engineering
Optimal phylogenetic reconstruction (CD, EM, SR), pp. 159–168.
STOC-2006-FatourouFR #implementation #trade-off
Time-space tradeoffs for implementations of snapshots (PF, FEF, ER), pp. 169–178.
STOC-2006-Ben-OrPV
Byzantine agreement in the full-information model in O(log n) rounds (MBO, EP, VV), pp. 179–186.
STOC-2006-Antonakopoulos #bound #performance #protocol
Fast leader-election protocols with bounded cheaters’ edge (SA), pp. 187–196.
STOC-2006-ChoG #distributed #multi #resource management
Pricing for fairness: distributed resource allocation for multiple objectives (SwC, AG), pp. 197–204.
STOC-2006-CharikarMM #algorithm #game studies
Near-optimal algorithms for unique games (MC, KM, YM), pp. 205–214.
STOC-2006-AroraC #approximate
New approximation guarantee for chromatic number (SA, EC), pp. 215–224.
STOC-2006-VassilevskaW #3d
Finding a maximum weight triangle in n3-Delta time, with applications (VV, RW), pp. 225–231.
STOC-2006-PatrascuT #trade-off
Time-space trade-offs for predecessor search (MP, MT), pp. 232–240.
STOC-2006-Dinur #theorem
The PCP theorem by gap amplification (ID), pp. 241–250.
STOC-2006-Shapira #all about #combinator #graph
A combinatorial characterization of the testable graph properties: it’s all about regularity (NA, EF, IN, AS), pp. 251–260.
STOC-2006-BorgsCLSSV #graph #parametricity #testing
Graph limits and parameter testing (CB, JTC, LL, VTS, BS, KV), pp. 261–270.
STOC-2006-AbrahamBN #metric #roadmap
Advances in metric embedding theory (IA, YB, ON), pp. 271–286.
STOC-2006-NguyenV #performance #proving
Zero knowledge with efficient provers (MHN, SPV), pp. 287–295.
STOC-2006-Watrous #quantum
Zero-knowledge against quantum attacks (JW), pp. 296–305.
STOC-2006-MicaliP
Local zero knowledge (SM, RP), pp. 306–315.
STOC-2006-RemyS #approximate
A quasi-polynomial time approximation scheme for minimum weight triangulation (JR, AS), pp. 316–325.
STOC-2006-Clarkson #using
Building triangulations using epsilon-nets (KLC), pp. 326–335.
STOC-2006-AsanoMT #distance
The distance trisector curve (TA, JM, TT), pp. 336–343.
STOC-2006-DinurMR #approximate
Conditional hardness for approximate coloring (ID, EM, OR), pp. 344–353.
STOC-2006-FellowsRRS #clique #np-hard
Clique-width minimization is NP-hard (MRF, FAR, UR, SS), pp. 354–362.
STOC-2006-Feldman #approximate #learning #logic #query
Hardness of approximate two-level logic minimization and PAC learning with membership queries (VF), pp. 363–372.
STOC-2006-Impagliazzo #algorithm #question #random
Can every randomized algorithm be derandomized? (RI), pp. 373–374.
STOC-2006-FeigeM
Finding small balanced separators (UF, MM), pp. 375–384.
STOC-2006-KhandekarRV #clustering #graph #using
Graph partitioning using single commodity flows (RK, SR, UVV), pp. 385–390.
STOC-2006-NesetrilM #algorithm #linear
Linear time low tree-width partitions and algorithmic consequences (JN, POdM), pp. 391–400.
STOC-2006-KawarabayashiM #approximate #graph
Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs (KiK, BM), pp. 401–416.
STOC-2006-Gurvits #algorithm #approach #bound #proving
Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications (LG), pp. 417–426.
STOC-2006-AharonovJL #algorithm #approximate #polynomial #quantum
A polynomial quantum algorithm for approximating the Jones polynomial (DA, VJ, ZL), pp. 427–436.
STOC-2006-DinurFKO #bound #fourier #on the
On the fourier tails of bounded functions over the discrete cube (ID, EF, GK, RO), pp. 437–446.
STOC-2006-RegevR #problem
Lattice problems and norm embeddings (OR, RR), pp. 447–456.
STOC-2006-ReingoldTV #graph #problem #pseudo
Pseudorandom walks on regular digraphs and the RL vs. L problem (OR, LT, SPV), pp. 457–466.
STOC-2006-Plandowski #algorithm #equation #performance #word
An efficient algorithm for solving word equations (WP), pp. 467–476.
STOC-2006-DeMarzoKM #algorithm #online #robust
Online trading algorithms and robust option pricing (PD, IK, YM), pp. 477–486.
STOC-2006-PanagiotouS #metric #on the #performance
On adequate performance measures for paging (KP, AS), pp. 487–496.
STOC-2006-Rao #constant #independence
Extractors for a constant number of polynomially small min-entropy independent sources (AR), pp. 497–506.
STOC-2006-Nordstrom #proving
Narrow proofs may be spacious: separating space and width in resolution (JN), pp. 507–516.
STOC-2006-AndrewsZ #problem
Logarithmic hardness of the directed congestion minimization problem (MA, LZ), pp. 517–526.
STOC-2006-ChuzhoyK #graph #problem
Hardness of cut problems in directed graphs (JC, SK), pp. 527–536.
STOC-2006-DevanurKSV #linear #problem
Integrality gaps for sparsest cut and minimum linear arrangement problems (NRD, SK, RS, NKV), pp. 537–546.
STOC-2006-KarloffKMR #distance #metric #on the
On earthmover distance, metric labeling, and 0-extension (HJK, SK, AM, YR), pp. 547–556.
STOC-2006-AilonC #approximate #nearest neighbour #performance
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform (NA, BC), pp. 557–563.
STOC-2006-AryaMM #on the
On the importance of idempotence (SA, TM, DMM), pp. 564–573.
STOC-2006-ColeG #bound #set
Searching dynamic point sets in spaces with bounded doubling dimension (RC, LAG), pp. 574–583.
STOC-2006-AngluinACW #injection #learning
Learning a circuit by injecting values (DA, JA, JC, YW), pp. 584–593.
STOC-2006-GavinskyKRW #bound #communication #complexity #exponential #identification #quantum
Bounded-error quantum state identification and exponential separations in communication complexity (DG, JK, OR, RdW), pp. 594–603.
STOC-2006-HallgrenMRRS #graph #morphism #quantum
Limitations of quantum coset states for graph isomorphism (SH, CM, MR, AR, PS), pp. 604–617.
STOC-2006-AmbainisSW #bound #quantum #theorem #trade-off
A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs (AA, RS, RdW), pp. 618–633.
STOC-2006-Zhang #bound #quantum #random
New upper and lower bounds for randomized and quantum local search (SZ), pp. 634–643.
STOC-2006-DobzinskiNS #combinator #random
Truthful randomized mechanisms for combinatorial auctions (SD, NN, MS), pp. 644–652.
STOC-2006-FischerRV #adaptation #convergence #performance
Fast convergence to Wardrop equilibria by adaptive sampling methods (SF, HR, BV), pp. 653–662.
STOC-2006-FleischerKLS #multi #probability
Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree (LF, JK, SL, GS), pp. 663–670.
STOC-2006-BarakRSW #graph
2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction (BB, AR, RS, AW), pp. 671–680.
STOC-2006-Zuckerman #clique #linear
Linear degree extractors and the inapproximability of max clique and chromatic number (DZ), pp. 681–690.
STOC-2006-KampRVZ
Deterministic extractors for small-space sources (JK, AR, SPV, DZ), pp. 691–700.
STOC-2006-AkaviaGGM #np-hard #on the
On basing one-way functions on NP-hardness (AA, OG, SG, DM), pp. 701–710.
STOC-2006-DubrovI #complexity #on the #performance
On the randomness complexity of efficient sampling (BD, YI), pp. 711–720.
STOC-2006-BansalCES #graph
A quasi-PTAS for unsplittable flow on line graphs (NB, AC, AE, BS), pp. 721–729.
STOC-2006-GargK
Minimizing average flow time on related machines (NG, AK), pp. 730–738.
STOC-2006-LeviRS #algorithm #modelling #probability
Provably near-optimal sampling-based algorithms for Stochastic inventory control models (RL, RR, DBS), pp. 739–748.
STOC-2006-Klein #graph #set
A subset spanner for Planar graphs, : with application to subset TSP (PNK), pp. 749–756.
STOC-2006-ChekuriKS #constant #graph
Edge-disjoint paths in Planar graphs with constant congestion (CC, SK, FBS), pp. 757–766.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.