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)

11 ×#graph
10 ×#algorithm
9 ×#problem
8 ×#approximate
8 ×#on the
7 ×#bound
7 ×#performance
6 ×#quantum
5 ×#random
4 ×#linear

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.