## Jon M. Kleinberg

*Proceedings of the 38th Annual ACM Symposium on Theory of Computing*

STOC, 2006.

@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.

11 ×#graph

10 ×#algorithm

9 ×#problem

8 ×#approximate

8 ×#on the

7 ×#bound

7 ×#performance

6 ×#quantum

5 ×#random

4 ×#linear

10 ×#algorithm

9 ×#problem

8 ×#approximate

8 ×#on the

7 ×#bound

7 ×#performance

6 ×#quantum

5 ×#random

4 ×#linear