## Lance Fortnow, Salil P. Vadhan

*Proceedings of the 43rd Annual ACM Symposium on Theory of Computing*

STOC, 2011.

@proceedings{STOC-2011, address = "San Jose, California, USA", editor = "Lance Fortnow and Salil P. Vadhan", isbn = "978-1-4503-0691-1", publisher = "{ACM}", title = "{Proceedings of the 43rd Annual ACM Symposium on Theory of Computing}", year = 2011, }

### Contents (84 items)

- STOC-2011-PatrascuT #power of
- The power of simple tabulation hashing (MP, MT), pp. 1–10.
- STOC-2011-LenzenW #bound #parallel #random
- Tight bounds for parallel randomized load balancing: extended abstract (CL, RW), pp. 11–20.
- STOC-2011-DoerrFF #network #social
- Social networks spread rumors in sublogarithmic time (BD, MF, TF), pp. 21–30.
- STOC-2011-RegevK #communication #quantum
- Quantum one-way communication can be exponentially stronger than classical communication (OR, BK), pp. 31–40.
- STOC-2011-Sherstov #communication #complexity #quantum #query #theorem
- Strong direct product theorems for quantum communication and query complexity (AAS), pp. 41–50.
- STOC-2011-ChakrabartiR #bound #communication #complexity
- An optimal lower bound on the communication complexity of gap-hamming-distance (AC, OR), pp. 51–60.
- STOC-2011-DingLP #metric
- Cover times, blanket times, and majorizing measures (JD, JRL, YP), pp. 61–70.
- STOC-2011-FungHHP #framework #graph
- A general framework for graph sparsification (WSF, RH, NJAH, DP), pp. 71–80.
- STOC-2011-KawarabayashiK #algorithm #approximate #problem
- Breaking o(n1/2)-approximation algorithms for the edge-disjoint paths problem with congestion two (KiK, YK), pp. 81–88.
- STOC-2011-HolensteinKT #equivalence #random #revisited
- The equivalence of the random oracle model and the ideal cipher model, revisited (TH, RK, ST), pp. 89–98.
- STOC-2011-GentryW
- Separating succinct non-interactive arguments from all falsifiable assumptions (CG, DW), pp. 99–108.
- STOC-2011-Pass #security #standard
- Limits of provable security from standard assumptions (RP), pp. 109–118.
- STOC-2011-PapadimitriouP #on the
- On optimal single-item auctions (CHP, GP), pp. 119–128.
- STOC-2011-DobzinskiFK #correlation
- Optimal auctions with correlated bidders are easy (SD, HF, RDK), pp. 129–138.
- STOC-2011-Dobzinski #combinator
- An impossibility result for truthful combinatorial auctions with submodular valuations (SD), pp. 139–148.
- STOC-2011-DughmiRY #combinator #optimisation #random #towards
- From convex optimization to randomized mechanisms: toward optimal combinatorial auctions (SD, TR, QY), pp. 149–158.
- STOC-2011-BravermanR #communication #fault #interactive #towards
- Towards coding for maximum errors in interactive communication (MB, AR), pp. 159–166.
- STOC-2011-KoppartySY
- High-rate codes with sublinear-time decoding (SK, SS, SY), pp. 167–176.
- STOC-2011-ZewiB #approximate
- From affine to two-source extractors via approximate duality (NZ, EBS), pp. 177–186.
- STOC-2011-HatamiL #correlation #fault #invariant #testing
- Correlation testing for affine invariant properties on Fpn in the high error regime (HH, SL), pp. 187–194.
- STOC-2011-AdsulGMS #algorithm #game studies #morphism #polynomial
- Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm (BA, JG, RM, MAS), pp. 195–204.
- STOC-2011-HansenKLMT #algorithm #game studies #probability
- Exact algorithms for solving stochastic games: extended abstract (KAH, MK, NL, PBM, EPT), pp. 205–214.
- STOC-2011-ImmorlicaKLMPT #algorithm
- Dueling algorithms (NI, ATK, BL, AM, AP, MT), pp. 215–224.
- STOC-2011-MoitraO
- Pareto optimal solutions for smoothed analysts (AM, RO), pp. 225–234.
- STOC-2011-KolipakaS
- Moser and tardos meet Lovász (KBRK, MS), pp. 235–244.
- STOC-2011-MoserS #algorithm #satisfiability
- A full derandomization of schöning’s k-SAT algorithm (RAM, DS), pp. 245–252.
- STOC-2011-GopalanMRZ #combinator #generative #pseudo
- Pseudorandom generators for combinatorial shapes (PG, RM, OR, DZ), pp. 253–262.
- STOC-2011-KouckyNP #generative #pseudo
- Pseudorandom generators for group products: extended abstract (MK, PN, PP), pp. 263–272.
- STOC-2011-ChristianoKMST #approximate #graph #performance
- Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs (PC, JAK, AM, DAS, SHT), pp. 273–282.
- STOC-2011-FriedmannHZ #algorithm #bound #random
- Subexponential lower bounds for randomized pivoting rules for the simplex algorithm (OF, TDH, UZ), pp. 283–292.
- STOC-2011-Haeupler #network
- Analyzing network coding gossip made easy (BH), pp. 293–302.
- STOC-2011-Chuzhoy #algorithm #graph #problem
- An algorithm for the graph crossing number problem (JC), pp. 303–312.
- STOC-2011-ItalianoNSW #algorithm #graph
- Improved algorithms for min cut and max flow in undirected planar graphs (GFI, YN, PS, CWN), pp. 313–322.
- STOC-2011-DinitzK #linear #source code
- Directed spanners via flow-based linear programs (MD, RK), pp. 323–332.
- STOC-2011-AaronsonA #complexity #linear
- The computational complexity of linear optics (SA, AA), pp. 333–342.
- STOC-2011-BrandaoCY #algorithm #problem #quantum
- A quasipolynomial-time algorithm for the quantum separability problem (FGSLB, MC, JY), pp. 343–352.
- STOC-2011-KempeV #game studies #parallel
- Parallel repetition of entangled games (JK, TV), pp. 353–362.
- STOC-2011-SarmaHKKNPPW #approximate #distributed #verification
- Distributed verification and hardness of distributed approximation (ADS, SH, LK, AK, DN, GP, DP, RW), pp. 363–372.
- STOC-2011-GolabHW #distributed #implementation #random
- Linearizable implementations do not suffice for randomized distributed computation (WMG, LH, PW), pp. 373–382.
- STOC-2011-KantorLPP #communication
- The topology of wireless communication (EK, ZL, MP, DP), pp. 383–392.
- STOC-2011-GiakkoupisS #matter
- Optimal path search in small worlds: dimension matters (GG, NS), pp. 393–402.
- STOC-2011-NovocinSV #algorithm #complexity
- An LLL-reduction algorithm with quasi-linear time complexity: extended abstract (AN, DS, GV), pp. 403–412.
- STOC-2011-KhotM #approximate #equation #linear #np-hard
- NP-hardness of approximately solving linear equations over reals (SK, DM), pp. 413–420.
- STOC-2011-SarafV #black box #multi #testing
- Black-box identity testing of depth-4 multilinear circuits (SS, IV), pp. 421–430.
- STOC-2011-SaxenaS #bound #matter #testing
- Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn’t matter (NS, CS), pp. 431–440.
- STOC-2011-DemaineHK #algorithm #composition #graph
- Contraction decomposition in h-minor-free graphs and algorithmic applications (EDD, MH, KiK), pp. 441–450.
- STOC-2011-KawarabayashiW #algorithm #composition #graph #proving
- A simpler algorithm and shorter proof for the graph minor decomposition (KiK, PW), pp. 451–458.
- STOC-2011-BousquetDT #multi
- Multicut is FPT (NB, JD, ST), pp. 459–468.
- STOC-2011-MarxR #multi #parametricity
- Fixed-parameter tractability of multicut parameterized by the size of the cutset (DM, IR), pp. 469–478.
- STOC-2011-GroheKMW #parametricity
- Finding topological subgraphs is fixed-parameter tractable (MG, KiK, DM, PW), pp. 479–488.
- STOC-2011-Kopparty #complexity #finite #on the
- On the complexity of powering in finite fields (SK), pp. 489–498.
- STOC-2011-ChienHSS #commutative
- Almost settling the hardness of noncommutative determinant (SC, PH, AS, SS), pp. 499–508.
- STOC-2011-BurgisserI #complexity #geometry #rank
- Geometric complexity theory and tensor rank (PB, CI), pp. 509–518.
- STOC-2011-BarakDYW #bound #design #geometry #matrix #rank
- Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes (BB, ZD, AY, AW), pp. 519–528.
- STOC-2011-KleinbergO
- Mechanisms for (mis)allocating scientific credit (JMK, SO), pp. 529–538.
- STOC-2011-ColeCGMO #coordination
- Inner product spaces for MinSum coordination mechanisms (RC, JRC, VG, VSM, NO), pp. 539–548.
- STOC-2011-FeigeT #design #nondeterminism
- Mechanism design with uncertain inputs: (to err is human, to forgive divine) (UF, MT), pp. 549–558.
- STOC-2011-PatrascuT11a
- Don’t rush into a union: take time to find your roots (MP, MT), pp. 559–568.
- STOC-2011-FeldmanL #approximate #clustering #framework
- A unified framework for approximating and clustering data (DF, ML), pp. 569–578.
- STOC-2011-AryaFM #approximate #query
- Approximate polytope membership queries (SA, GDdF, DMM), pp. 579–586.
- STOC-2011-KarandeMT #online
- Online bipartite matching with unknown distributions (CK, AM, PT), pp. 587–596.
- STOC-2011-MahdianY #approach #online #random
- Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs (MM, QY), pp. 597–606.
- STOC-2011-AdamaszekCER #bound #order
- Almost tight bounds for reordering buffer management (AA, AC, ME, HR), pp. 607–616.
- STOC-2011-Svensson
- Santa Claus schedules jobs on unrelated machines (OS), pp. 617–626.
- STOC-2011-IndykP #clustering #distance #modelling
- K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance (PI, EP), pp. 627–636.
- STOC-2011-BourgainDFKK #matrix
- Breaking the k2 barrier for explicit RIP matrices (JB, SJD, KF, SK, DK), pp. 637–644.
- STOC-2011-Karnin
- Deterministic construction of a high dimensional lp section in l1n for any p<2 (ZSK), pp. 645–654.
- STOC-2011-BodirskyP #graph #theorem
- Schaefer’s theorem for graphs (MB, MP), pp. 655–664.
- STOC-2011-Yoshida #algorithm #approximate #bound #csp
- Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP (YY), pp. 665–674.
- STOC-2011-NewmanS #graph
- Every property of hyperfinite graphs is testable (IN, CS), pp. 675–684.
- STOC-2011-ValiantV
- Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs (GV, PV), pp. 685–694.
- STOC-2011-Goyal #constant #protocol #using
- Constant round non-malleable protocols using one way functions (VG), pp. 695–704.
- STOC-2011-LinP
- Constant-round non-malleable commitments from any one-way function (HL, RP), pp. 705–714.
- STOC-2011-Ajtai
- Secure computation with information leaking to an adversary (MA), pp. 715–724.
- STOC-2011-LewkoLW #how
- How to leak on key updates (ABL, ML, BW), pp. 725–734.
- STOC-2011-Woodruff #approximate #black box #protocol
- Near-optimal private approximation protocols via a black box transformation (DPW), pp. 735–744.
- STOC-2011-KaneNPW #data type #estimation #performance
- Fast moment estimation in data streams in optimal space (DMK, JN, EP, DPW), pp. 745–754.
- STOC-2011-SohlerW
- Subspace embeddings for the L1-norm with applications (CS, DPW), pp. 755–764.
- STOC-2011-LeeS #bound
- Near-optimal distortion bounds for embedding doubling spaces into L1 (JRL, AS), pp. 765–772.
- STOC-2011-FawziHS #nondeterminism #performance
- From low-distortion norm embeddings to explicit uncertainty relations and efficient information locking (OF, PH, PS), pp. 773–782.
- STOC-2011-VondrakCZ #multi
- Submodular function maximization via the multilinear relaxation and contention resolution schemes (JV, CC, RZ), pp. 783–792.
- STOC-2011-BalcanH #learning
- Learning submodular functions (MFB, NJAH), pp. 793–802.
- STOC-2011-GuptaHRU #query #statistics
- Privately releasing conjunctions and the statistical query barrier (AG, MH, AR, JU), pp. 803–812.
- STOC-2011-Smith #convergence #estimation #privacy #statistics
- Privacy-preserving statistical estimation with optimal convergence rates (AS), pp. 813–822.

13 ×#algorithm

9 ×#approximate

8 ×#bound

8 ×#graph

6 ×#complexity

6 ×#random

5 ×#communication

4 ×#multi

3 ×#combinator

3 ×#game studies

9 ×#approximate

8 ×#bound

8 ×#graph

6 ×#complexity

6 ×#random

5 ×#communication

4 ×#multi

3 ×#combinator

3 ×#game studies