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

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

10 ×#bound

8 ×#graph

8 ×#on the

7 ×#algorithm

7 ×#polynomial

7 ×#problem

6 ×#approximate

5 ×#complexity

5 ×#random

4 ×#multi

8 ×#graph

8 ×#on the

7 ×#algorithm

7 ×#polynomial

7 ×#problem

6 ×#approximate

5 ×#complexity

5 ×#random

4 ×#multi