Leonard J. Schulman
Proceedings of the 42nd Annual ACM Symposium on Theory of Computing
STOC, 2010.

@proceedings{STOC-2010,
	address       = "Cambridge, Massachusetts, USA",
	editor        = "Leonard J. Schulman",
	isbn          = "978-1-4503-0050-6",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 42nd Annual ACM Symposium on Theory of Computing}",
	year          = 2010,
}

Contents (82 items)

10 ×#bound
8 ×#graph
8 ×#on the
7 ×#algorithm
7 ×#polynomial
7 ×#problem
6 ×#approximate
5 ×#complexity
5 ×#random
4 ×#multi

STOC-2010-Kannan #matrix

Spectral methods for matrices and tensors (RK), pp. 1–12.

STOC-2010-Talagrand #question #set

Are many small sets explicitly small? (MT), pp. 13–36.

STOC-2010-Montanari #algorithm #message passing

Message passing algorithms: a success looking for theoreticians (AM), pp. 37–38.

STOC-2010-GoelKK #graph

Perfect matchings in o(n log n) time in regular bipartite graphs (AG, MK, SK), pp. 39–46.

STOC-2010-LeightonM

Extensions and limits to vertex sparsification (FTL, AM), pp. 47–56.

STOC-2010-KollaMST

Subgraph sparsification and nearly optimal ultrasparsifiers (AK, YM, AS, SHT), pp. 57–66.

STOC-2010-BarakBCR #communication #how #interactive

How to compress interactive communication (BB, MB, XC, AR), pp. 67–76.

STOC-2010-Klauck #theorem

A strong direct product theorem for disjointness (HK), pp. 77–86.

STOC-2010-BeameHP #complexity #proving

Hardness amplification in proof complexity (PB, TH, TP), pp. 87–96.

STOC-2010-GaoW #random

Load balancing and orientability thresholds for random hypergraphs (PG, NCW), pp. 97–104.

STOC-2010-BayatiGT #approach #combinator #graph #random #scalability

Combinatorial approach to the interpolation method and scaling limits in sparse random graphs (MB, DG, PT), pp. 105–114.

STOC-2010-Hirai #bound #multi #problem

The maximum multiflow problems with bounded fractionality (HH), pp. 115–120.

STOC-2010-Madry #algorithm #approximate #graph #multi #performance #problem

Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms (AM), pp. 121–130.

STOC-2010-AaronsonD #quantum

A full characterization of quantum advice (SA, AD), pp. 131–140.

STOC-2010-Aaronson #polynomial

BQP and the polynomial hierarchy (SA), pp. 141–150.

STOC-2010-AmbainisKS #quantum

A quantum lovász local lemma (AA, JK, OS), pp. 151–160.

STOC-2010-DeV #quantum

Near-optimal extractors against quantum storage (AD, TV), pp. 161–170.

STOC-2010-ApplebaumBW #encryption

Public-key cryptography from different assumptions (BA, BB, AW), pp. 171–180.

STOC-2010-Ajtai

Oblivious RAMs without cryptogrpahic assumptions (MA), pp. 181–190.

STOC-2010-GoyalJ #complexity #on the

On the round complexity of covert computation (VG, AJ), pp. 191–200.

STOC-2010-BhaskaraCCFV #approximate #detection

Detecting high log-densities: an O(n1/4) approximation for densest k-subgraph (AB, MC, EC, UF, AV), pp. 201–210.

STOC-2010-BateniHM #approximate #bound #graph

Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth (MB, MH, DM), pp. 211–220.

STOC-2010-DeyHK #linear #programming

Optimal homologous cycles, total unimodularity, and linear programming (TKD, ANH, BK), pp. 221–230.

STOC-2010-Williams #bound

Improving exhaustive search implies superpolynomial lower bounds (RW), pp. 231–240.

STOC-2010-PaturiP #complexity #on the #satisfiability

On the complexity of circuit satisfiability (RP, PP), pp. 241–250.

STOC-2010-DellM #polynomial #satisfiability

Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses (HD, DvM), pp. 251–260.

STOC-2010-MagniezMN #streaming

Recognizing well-parenthesized expressions in the streaming model (FM, CM, AN), pp. 261–270.

STOC-2010-BravermanO #dataset #independence

Measuring independence of datasets (VB, RO), pp. 271–280.

STOC-2010-BravermanO10a

Zero-one frequency laws (VB, RO), pp. 281–290.

STOC-2010-Orlin #algorithm

Improved algorithms for computing fisher’s market clearing prices: computing fisher’s market clearing prices (JBO), pp. 291–300.

STOC-2010-HartlineL #algorithm #design

Bayesian algorithmic mechanism design (JDH, BL), pp. 301–310.

STOC-2010-ChawlaHMS #design #multi

Multi-parameter mechanism design and sequential posted pricing (SC, JDH, DLM, BS), pp. 311–320.

STOC-2010-LokshtanovN #algebra

Saving space by algebraization (DL, JN), pp. 321–330.

STOC-2010-HaramatyS #on the #polynomial

On the structure of cubic and quartic polynomials (EH, AS), pp. 331–340.

STOC-2010-DasguptaKS

A sparse Johnson: Lindenstrauss transform (AD, RK, TS), pp. 341–350.

STOC-2010-MicciancioV #algorithm #exponential #problem

A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations (DM, PV), pp. 351–358.

STOC-2010-CardinalFJJM #algorithm #sorting

Sorting under partial information (without the ellipsoid algorithm) (JC, SF, GJ, RMJ, JIM), pp. 359–368.

STOC-2010-LeeSV #power of

Matroid matching: the power of local search (JL, MS, JV), pp. 369–378.

STOC-2010-BhattacharyaGGM

Budget constrained auctions with heterogeneous items (SB, GG, SG, KM), pp. 379–388.

STOC-2010-FraigniaudG #network #on the

On the searchability of small-world networks with arbitrary underlying structure (PF, GG), pp. 389–398.

STOC-2010-ChierichettiLP #bound

Almost tight bounds for rumour spreading with conductance (FC, SL, AP), pp. 399–408.

STOC-2010-GuruswamiHK #linear #on the #random

On the list-decodability of random linear codes (VG, JH, SK), pp. 409–416.

STOC-2010-KoppartyS #fault #linear #random #testing

Local list-decoding and testing of random linear codes from high error (SK, SS), pp. 417–426.

STOC-2010-MekaZ #generative #polynomial #pseudo

Pseudorandom generators for polynomial threshold functions (RM, DZ), pp. 427–436.

STOC-2010-HaitnerRV #generative #performance #pseudo

Efficiency improvements in constructing pseudorandom generators from one-way functions (IH, OR, SPV), pp. 437–446.

STOC-2010-VerbinZ #bound #memory management

The limits of buffering: a tight lower bound for dynamic membership in the external memory model (EV, QZ), pp. 447–456.

STOC-2010-OnakR #maintenance #scalability

Maintaining a large matching and a small vertex cover (KO, RR), pp. 457–464.

STOC-2010-DuanP #graph

Connectivity oracles for failure prone graphs (RD, SP), pp. 465–474.

STOC-2010-GilbertLPS #approximate #metric #optimisation

Approximate sparse recovery: optimizing time and measurements (ACG, YL, EP, MJS), pp. 475–484.

STOC-2010-GodoyGRA #decidability #problem

The HOM problem is decidable (GG, OG, LR, CÀ), pp. 485–494.

STOC-2010-KawamuraC #analysis #complexity

Complexity theory for operators in analysis (AK, SAC), pp. 495–502.

STOC-2010-BurgisserC #equation #polynomial #problem

Solving polynomial equations in smoothed polynomial time and a near solution to smale’s 17th problem (PB, FC), pp. 503–512.

STOC-2010-KuhnLO #distributed #network

Distributed computation in dynamic networks (FK, NAL, RO), pp. 513–522.

STOC-2010-Sherstov #bound

Optimal bounds for sign-representing the intersection of two halfspaces by polynomials (AAS), pp. 523–532.

STOC-2010-DiakonikolasHKMRST #bound #polynomial

Bounding the average sensitivity and noise sensitivity of polynomial threshold functions (ID, PH, AK, RM, PR, RAS, LYT), pp. 533–542.

STOC-2010-HarshaKM

An invariance principle for polytopes (PH, AK, RM), pp. 543–552.

STOC-2010-KalaiMV #learning

Efficiently learning mixtures of two Gaussians (ATK, AM, GV), pp. 553–562.

STOC-2010-Vegh

Augmenting undirected node-connectivity by one (LAV), pp. 563–572.

STOC-2010-JainJUW

QIP = PSPACE (RJ, ZJ, SU, JW), pp. 573–582.

STOC-2010-ByrkaGRS #approximate

An improved LP-based approximation for steiner tree (JB, FG, TR, LS), pp. 583–592.

STOC-2010-DodisPT

Changing base without losing space (YD, MP, MT), pp. 593–602.

STOC-2010-Patrascu #bound #polynomial #problem #towards

Towards polynomial lower bounds for dynamic problems (MP), pp. 603–610.

STOC-2010-FraigniaudK

An optimal ancestry scheme and small universal posets (PF, AK), pp. 611–620.

STOC-2010-LeeM #metric

Bilipschitz snowflakes and metrics of negative type (JRL, MM), pp. 621–630.

STOC-2010-RaghavendraST #approximate #graph #parametricity

Approximations for the isoperimetric and spectral profile of graphs and related parameters (PR, DS, PT), pp. 631–640.

STOC-2010-Varadarajan #geometry #set

Weighted geometric set cover via quasi-uniform sampling (KRV), pp. 641–648.

STOC-2010-KarninMSV #bound #multi #testing

Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in (ZSK, PM, AS, IV), pp. 649–658.

STOC-2010-Raz #bound

Tensor-rank and lower bounds for arithmetic formulas (RR), pp. 659–666.

STOC-2010-HrubesWY #commutative #problem

Non-commutative circuits and the sum-of-squares problem (PH, AW, AY), pp. 667–676.

STOC-2010-ArvindS #commutative #on the

On the hardness of the noncommutative determinant (VA, SS), pp. 677–686.

STOC-2010-KawarabayashiW #algorithm #graph #proving #theorem

A shorter proof of the graph minor algorithm: the unique linkage theorem (KiK, PW), pp. 687–694.

STOC-2010-KawarabayashiR

Odd cycle packing (KiK, BAR), pp. 695–704.

STOC-2010-HardtT #difference #geometry #on the #privacy

On the geometry of differential privacy (MH, KT), pp. 705–714.

STOC-2010-DworkNPR #difference #privacy

Differential privacy under continual observation (CD, MN, TP, GNR), pp. 715–724.

STOC-2010-DyerR #complexity #csp #on the

On the complexity of #CSP (MED, DR), pp. 725–734.

STOC-2010-Marx #constraints #query

Tractable hypergraph properties for constraint satisfaction and conjunctive queries (DM), pp. 735–744.

STOC-2010-Svensson #precedence #scheduling

Conditional hardness of precedence constrained scheduling on identical machines (OS), pp. 745–754.

STOC-2010-RaghavendraS #game studies #graph

Graph expansion and the unique games conjecture (PR, DS), pp. 755–764.

STOC-2010-RothR #interactive #privacy

Interactive privacy via the median mechanism (AR, TR), pp. 765–774.

STOC-2010-KasiviswanathanRSU #correlation #matrix #random

The price of privately releasing contingency tables and the spectra of random matrices with correlated rows (SPK, MR, AS, JU), pp. 775–784.

STOC-2010-ChandranKOR #privacy

Privacy amplification with asymptotically optimal entropy loss (NC, BK, RO, LR), pp. 785–794.

STOC-2010-AkaviaGGM #np-hard

Erratum for: on basing one-way functions on NP-hardness (AA, OG, SG, DM), pp. 795–796.