Proceedings of the 43rd Annual ACM Symposium on Theory of Computing
BibSLEIGH corpus
BibSLEIGH tags
BibSLEIGH bundles
BibSLEIGH people
EDIT!
CC-BY
Open Knowledge
XHTML 1.0 W3C Rec
CSS 2.1 W3C CanRec
email twitter

Lance Fortnow, Salil P. Vadhan
Proceedings of the 43rd Annual ACM Symposium on Theory of Computing
STOC, 2011.

TCS
DBLP
Scholar
Full names Links ISxN
@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.

Bibliography of Software Language Engineering in Generated Hypertext (BibSLEIGH) is created and maintained by Dr. Vadim Zaytsev.
Hosted as a part of SLEBOK on GitHub.