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)

13 ×#algorithm
9 ×#approximate
8 ×#bound
8 ×#graph
6 ×#complexity
6 ×#random
5 ×#communication
4 ×#multi
3 ×#combinator
3 ×#game studies

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.