Michael Mitzenmacher
Proceedings of the 41st Annual ACM Symposium on Theory of Computing
STOC, 2009.

@proceedings{STOC-2009,
	address       = "Bethesda, Maryland, USA",
	editor        = "Michael Mitzenmacher",
	isbn          = "978-1-60558-506-2",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 41st Annual ACM Symposium on Theory of Computing}",
	year          = 2009,
}

Contents (79 items)

8 ×#algorithm
7 ×#on the
5 ×#approximate
5 ×#linear
4 ×#graph
4 ×#performance
4 ×#problem
4 ×#quantum
4 ×#random
3 ×#bound

STOC-2009-Wigderson

The work of Leslie Valiant (AW), pp. 1–2.

STOC-2009-AroraDS #algorithm #message passing

Message passing algorithms and improved LP decoding (SA, CD, DS), pp. 3–12.

STOC-2009-GopalanGR

List decoding tensor products and interleaved codes (PG, VG, PR), pp. 13–22.

STOC-2009-Guruswami #morphism

Artin automorphisms, cyclotomic function fields, and folded list-decodable codes (VG), pp. 23–32.

STOC-2009-ChengW #distance #problem #reduction

A deterministic reduction for the gap minimum distance problem: [extended abstract] (QC, DW), pp. 33–38.

STOC-2009-Efremenko

3-query locally decodable codes of subexponential length (KE), pp. 39–44.

STOC-2009-Sellie #learning #random

Exact learning of random DNF over the uniform distribution (LS), pp. 45–54.

STOC-2009-BabaiBS #matrix #polynomial

Polynomial-time theory of matrix groups (LB, RB, ÁS), pp. 55–64.

STOC-2009-Ben-SassonK

Affine dispersers from subspace polynomials (EBS, SK), pp. 65–74.

STOC-2009-DaskalakisP #equilibrium #nash #on the

On oblivious PTAS’s for nash equilibrium (CD, CHP), pp. 75–84.

STOC-2009-Gafni

The extended BG-simulation and the characterization of t-resiliency (EG), pp. 85–92.

STOC-2009-CardinalFJJM #algorithm #partial order #performance

An efficient algorithm for partial order production (JC, SF, GJ, RMJ, JIM), pp. 93–100.

STOC-2009-BernsteinK

A nearly optimal oracle for avoiding failed vertices and edges (AB, DRK), pp. 101–110.

STOC-2009-BarenboimE #distributed #linear

Distributed (delta+1)-coloring in linear (in delta) time (LB, ME), pp. 111–120.

STOC-2009-FriedrichS #random

Near-perfect load balancing by randomized rounding (TF, TS), pp. 121–130.

STOC-2009-ImpagliazzoKW

New direct-product testers and 2-query PCPs (RI, VK, AW), pp. 131–140.

STOC-2009-GoldreichR #on the #proximity #testing

On proximity oblivious testing (OG, DR), pp. 141–150.

STOC-2009-Blais #testing

Testing juntas nearly optimally (EB), pp. 151–158.

STOC-2009-Shapira #invariant #testing

Green’s conjecture and testing linear-invariant properties (AS), pp. 159–166.

STOC-2009-Goldwasser #question #source code

Athena lecture: Controlling Access to Programs? (SG), pp. 167–168.

STOC-2009-Gentry #encryption #using

Fully homomorphic encryption using ideal lattices (CG), pp. 169–178.

STOC-2009-LinPV #concurrent #framework #security

A unified framework for concurrent security: universal composability from stand-alone non-malleability (HL, RP, MV), pp. 179–188.

STOC-2009-LinP

Non-malleability amplification (HL, RP), pp. 189–198.

STOC-2009-AndoniO #approximate #distance #edit distance

Approximating edit distance in near-linear time (AA, KO), pp. 199–204.

STOC-2009-ClarksonW #algebra #linear #streaming

Numerical linear algebra in the streaming model (KLC, DPW), pp. 205–214.

STOC-2009-NguyenDT #algorithm #approximate #matrix #performance #rank

A fast and efficient algorithm for low-rank approximation of a matrix (NHN, TTD, TDT), pp. 215–224.

STOC-2009-YoshidaYI #algorithm #approximate

An improved constant-time approximation algorithm for maximum~matchings (YY, MY, HI), pp. 225–234.

STOC-2009-AndersenP #evolution #set #using

Finding sparse cuts locally using evolving sets (RA, YP), pp. 235–244.

STOC-2009-LeeS #geometry #graph #on the

On the geometry of graphs with a forbidden minor (JRL, AS), pp. 245–254.

STOC-2009-BatsonSS

Twice-ramanujan sparsifiers (JDB, DAS, NS), pp. 255–262.

STOC-2009-Trevisan

Max cut and the smallest eigenvalue (LT), pp. 263–272.

STOC-2009-ChambersEN

Homology flows, cohomology cuts (EWC, JE, AN), pp. 273–282.

STOC-2009-CharikarMM

Integrality gaps for Sherali-Adams relaxations (MC, KM, YM), pp. 283–292.

STOC-2009-MathieuS

Sherali-adams relaxations of the matching polytope (CM, AS), pp. 293–302.

STOC-2009-Tulsiani #csp #reduction

CSP gaps and reductions in the lasserre hierarchy (MT), pp. 303–312.

STOC-2009-KarpinskiS #approximate #game studies #linear #problem

Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems (MK, WS), pp. 313–322.

STOC-2009-LeeMNS #constraints

Non-monotone submodular maximization under matroid and knapsack constraints (JL, VSM, VN, MS), pp. 323–332.

STOC-2009-Peikert #problem #worst-case

Public-key cryptosystems from the worst-case shortest vector problem: extended abstract (CP), pp. 333–342.

STOC-2009-Moser #proving

A constructive proof of the Lovász local lemma (RAM), pp. 343–350.

STOC-2009-GhoshRS #privacy

Universally utility-maximizing privacy mechanisms (AG, TR, MS), pp. 351–360.

STOC-2009-FeldmanFKN

Private coresets (DF, AF, HK, KN), pp. 361–370.

STOC-2009-DworkL #difference #privacy #robust #statistics

Differential privacy and robust statistics (CD, JL), pp. 371–380.

STOC-2009-DworkNRRV #algorithm #complexity #on the #performance

On the complexity of differentially private data release: efficient algorithms and hardness results (CD, MN, OR, GNR, SPV), pp. 381–390.

STOC-2009-Liu #algorithm #quantum #using

Quantum algorithms using the curvelet transform (YKL), pp. 391–400.

STOC-2009-Ta-Shma #quantum

Short seed extractors against quantum storage (ATS), pp. 401–408.

STOC-2009-CleveGMSY #algorithm #performance #quantum #query #simulation

Efficient discrete-time simulations of continuous-time quantum query algorithms (RC, DG, MM, RDS, DLYM), pp. 409–416.

STOC-2009-AharonovALV #detection #quantum

The detectability lemma and quantum gap amplification (DA, IA, ZL, UVV), pp. 417–426.

STOC-2009-LattanziS #network

Affiliation networks (SL, DS), pp. 427–434.

STOC-2009-ChechikLPR #fault tolerance #graph

Fault-tolerant spanners for general graphs (SC, ML, DP, LR), pp. 435–444.

STOC-2009-KawarabayashiR #decidability

Hadwiger’s conjecture is decidable (KiK, BAR), pp. 445–454.

STOC-2009-VassilevskaW

Finding, minimizing, and counting weighted subgraphs (VV, RW), pp. 455–464.

STOC-2009-KushilevitzW #communication #complexity #on the

On the complexity of communication complexity (EK, EW), pp. 465–474.

STOC-2009-Viola #bound #data type

Bit-probe lower bounds for succinct data structures (EV), pp. 475–482.

STOC-2009-AustrinH #independence

Randomly supported independence and resistance (PA, JH), pp. 483–492.

STOC-2009-ODonnellW #satisfiability

Conditional hardness for satisfiable 3-CSPs (RO, YW), pp. 493–502.

STOC-2009-ChenM #approach #design

A new approach to auctions and resilient mechanism design (JC, SM), pp. 503–512.

STOC-2009-Roughgarden #robust

Intrinsic robustness of the price of anarchy (TR), pp. 513–522.

STOC-2009-Even-DarMN #convergence #game studies #on the

On the convergence of regret minimization dynamics in concave games (EED, YM, UN), pp. 523–532.

STOC-2009-KleinbergPT #game studies #learning #multi

Multiplicative updates outperform generic no-regret learning in congestion games: extended abstract (RK, GP, ÉT), pp. 533–542.

STOC-2009-BateniCG #bound

MaxMin allocation via degree lower-bounded arborescences (MB, MC, VG), pp. 543–552.

STOC-2009-MontenegroT #how #question

How long does it take to catch a wild kangaroo? (RM, PT), pp. 553–560.

STOC-2009-KannanN #linear #programming #random

Random walks on polytopes and an affine interior point method for linear programming (RK, HN), pp. 561–570.

STOC-2009-MartinelliS

Mixing time for the solid-on-solid model (FM, AS), pp. 571–580.

STOC-2009-Sly #re-engineering

Reconstruction for the Potts model (AS), pp. 581–590.

STOC-2009-DietzfelbingerW #bound

Tight lower bounds for greedy routing in uniform small world rings (MD, PW), pp. 591–600.

STOC-2009-DodisW #encryption #symmetry

Non-malleable extractors and symmetric key cryptography from weak secrets (YD, DW), pp. 601–610.

STOC-2009-HaitnerRVW

Inaccessible entropy (IH, OR, SPV, HW), pp. 611–620.

STOC-2009-DodisKL #encryption #on the

On cryptography with auxiliary input (YD, YTK, SL), pp. 621–630.

STOC-2009-ChalopinG #graph

Every planar graph is the intersection graph of segments in the plane: extended abstract (JC, DG), pp. 631–638.

STOC-2009-AronovES

Small-size epsilon-nets for axis-parallel rectangles and boxes (BA, EE, MS), pp. 639–648.

STOC-2009-RabaniS #linear

Explicit construction of a small epsilon-net for linear threshold functions (YR, AS), pp. 649–658.

STOC-2009-GuptaK #approximate #probability

A constant-factor approximation for stochastic Steiner forest (AG, AK), pp. 659–668.

STOC-2009-AzarGY #multi #ranking

Multiple intents re-ranking (YA, IG, XY), pp. 669–678.

STOC-2009-ChadhaGKM #algorithm

A competitive algorithm for minimizing weighted flow time on unrelatedmachines with speed augmentation (JSC, NG, AK, VNM), pp. 679–684.

STOC-2009-GuptaKR #design #network #online #probability

Online and stochastic survivable network design (AG, RK, RR), pp. 685–694.

STOC-2009-ImpagliazzoKK #approach #axiom

An axiomatic approach to algebrization (RI, VK, AK), pp. 695–704.

STOC-2009-KolaitisK #graph #quantifier #random

Random graphs and the parity quantifier (PGK, SK), pp. 705–714.

STOC-2009-CaiLX #csp #problem

Holant problems and counting CSP (JyC, PL, MX), pp. 715–724.

STOC-2009-KunS

A new line of attack on the dichotomy conjecture (GK, MS), pp. 725–734.