## 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)

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

8 ×#algorithm

7 ×#on the

5 ×#approximate

5 ×#linear

4 ×#graph

4 ×#performance

4 ×#problem

4 ×#quantum

4 ×#random

3 ×#bound

7 ×#on the

5 ×#approximate

5 ×#linear

4 ×#graph

4 ×#performance

4 ×#problem

4 ×#quantum

4 ×#random

3 ×#bound