## David B. Shmoys

*Proceedings of the 46th Annual ACM Symposium on Theory of Computing*

STOC, 2014.

@proceedings{STOC-2014, acmid = "2591796", address = "New York, New York, USA", editor = "David B. Shmoys", isbn = "978-1-4503-2710-7", publisher = "{ACM}", title = "{Proceedings of the 46th Annual ACM Symposium on Theory of Computing}", year = 2014, }

### Contents (91 items)

- STOC-2014-BunUV #approximate #difference #privacy
- Fingerprinting codes and the price of approximate differential privacy (MB, JU, SPV), pp. 1–10.
- STOC-2014-DworkTT0 #analysis #bound #component #privacy
- Analyze gauss: optimal bounds for privacy-preserving principal component analysis (CD, KT, AT, LZ), pp. 11–20.
- STOC-2014-HsuHRRW
- Private matchings and allocations (JH, ZH, AR, TR, ZSW), pp. 21–30.
- STOC-2014-BarakKS
- Rounding sum-of-squares relaxations (BB, JAK, DS), pp. 31–40.
- STOC-2014-MakarychevMV #approximate #constant
- Constant factor approximation for balanced cut in the PIE model (KM, YM, AV), pp. 41–49.
- STOC-2014-SinghV #optimisation
- Entropy, optimization and counting (MS, NKV), pp. 50–59.
- STOC-2014-ChekuriC #bound #polynomial #theorem
- Polynomial bounds for the grid-minor theorem (CC, JC), pp. 60–69.
- STOC-2014-KawarabayashiKK #graph #grid #problem #theorem
- An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem (KiK, YK, SK), pp. 70–78.
- STOC-2014-AbrahamGGNT #composition #graph
- Cops, robbers, and threatening skeletons: padded decomposition for minor-free graphs (IA, CG, AG, ON, KT), pp. 79–88.
- STOC-2014-GroheKS #first-order #graph
- Deciding first-order properties of nowhere dense graphs (MG, SK, SS), pp. 89–98.
- STOC-2014-ArtemenkoS #generative #pseudo
- Pseudorandom generators with optimal seed length for non-boolean poly-size circuits (SA, RS), pp. 99–108.
- STOC-2014-GoldreichW #algorithm #on the
- On derandomizing algorithms that err extremely rarely (OG, AW), pp. 109–118.
- STOC-2014-KayalLSS #bound
- Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas (NK, NL, CS, SS), pp. 119–127.
- STOC-2014-FournierLMS #bound #matrix #multi
- Lower bounds for depth 4 formulas computing iterated matrix multiplication (HF, NL, GM, SS), pp. 128–135.
- STOC-2014-KumarS #all about #reduction
- The limits of depth reduction for arithmetic formulas: it’s all about the top fan-in (MK, SS), pp. 136–145.
- STOC-2014-KayalSS #bound
- A super-polynomial lower bound for regular arithmetic formulas (NK, CS, RS), pp. 146–153.
- STOC-2014-Belazzougui #linear
- Linear time construction of compressed text indices in compact space (DB), pp. 148–193.
- STOC-2014-Yoshida #composition #invariant #theorem
- A characterization of locally testable affine-invariant properties via decomposition theorems (YY), pp. 154–163.
- STOC-2014-BermanRY
- Lp-testing (PB, SR, GY), pp. 164–173.
- STOC-2014-LiNW #algorithm #linear #sketching #streaming
- Turnstile streaming algorithms might as well be linear sketches (YL, HLN, DPW), pp. 174–183.
- STOC-2014-Williams #algorithm #bound #linear
- New algorithms and lower bounds for circuits with linear threshold gates (RW), pp. 194–202.
- STOC-2014-Rossman #distance
- Formulas vs. circuits for small distance connectivity (BR), pp. 203–212.
- STOC-2014-GavinskyMWW #approach #bound #complexity #composition #towards
- Toward better formula lower bounds: an information complexity approach to the KRW composition conjecture (DG, OM, OW, AW), pp. 213–222.
- STOC-2014-Sherstov
- Breaking the minsky-papert barrier for constant-depth circuits (AAS), pp. 223–232.
- STOC-2014-DobzinskiNO #interactive #performance
- Economic efficiency requires interaction (SD, NN, SO), pp. 233–242.
- STOC-2014-ColeR #complexity
- The sample complexity of revenue maximization (RC, TR), pp. 243–252.
- STOC-2014-ChenGL
- Optimal competitive auctions (NC, NG, PL), pp. 253–262.
- STOC-2014-Rothvoss #complexity #exponential
- The matching polytope has exponential extension complexity (TR), pp. 263–272.
- STOC-2014-BravyiH
- Homological product codes (SB, MBH), pp. 273–282.
- STOC-2014-BerryCCKS #exponential #precise #simulation
- Exponential improvement in precision for simulating sparse Hamiltonians (DWB, AMC, RC, RK, RDS), pp. 283–292.
- STOC-2014-EisentragerHK0 #algorithm #quantum
- A quantum algorithm for computing the unit group of an arbitrary degree number field (KE, SH, AK, FS), pp. 293–302.
- STOC-2014-KesselheimTRV #online
- Primal beats dual on online packing LPs in the random-order model (TK, KR, AT, BV), pp. 303–312.
- STOC-2014-ImKM #algorithm #constraints #scheduling
- Competitive algorithms from competitive equilibria: non-clairvoyant scheduling under polyhedral constraints (SI, JK, KM), pp. 313–322.
- STOC-2014-CyganLPPS #parametricity
- Minimum bisection is fixed parameter tractable (MC, DL, MP, MP, SS), pp. 323–332.
- STOC-2014-PengS #linear #parallel #performance
- An efficient parallel solver for SDD linear systems (RP, DAS), pp. 333–342.
- STOC-2014-CohenKMPPRX #linear
- Solving SDD linear systems in nearly mlog1/2n time (MBC, RK, GLM, JWP, RP, AR, SCX), pp. 343–352.
- STOC-2014-BoutsidisW #matrix
- Optimal CUR matrix decompositions (CB, DPW), pp. 353–362.
- STOC-2014-Solomon #fault tolerance #metric
- From hierarchical partitions to hierarchical covers: optimal fault-tolerant spanners for doubling metrics (SS), pp. 363–372.
- STOC-2014-ChengJ
- Shortest paths on polyhedral surfaces and terrains (SWC, JJ), pp. 373–382.
- STOC-2014-ElberfeldK #bound #graph
- Embedding and canonizing graphs of bounded genus in logspace (ME, KiK), pp. 383–392.
- STOC-2014-Neeman #testing
- Testing surface area with arbitrary accuracy (JN), pp. 393–397.
- STOC-2014-BermanHT #bias #constant
- Coin flipping of any constant bias implies one-way functions (IB, IH, AT), pp. 398–407.
- STOC-2014-HaitnerT #protocol
- An almost-optimally fair three-party coin-flipping protocol (IH, ET), pp. 408–416.
- STOC-2014-MillerS #protocol #quantum #robust #using
- Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices (CAM, YS), pp. 417–426.
- STOC-2014-CoudronY #constant #infinity
- Infinite randomness expansion with a constant number of devices (MC, HY), pp. 427–436.
- STOC-2014-Kane
- The average sensitivity of an intersection of half spaces (DMK), pp. 437–440.
- STOC-2014-DanielyLS #complexity #learning
- From average case complexity to improper learning complexity (AD, NL, SSS), pp. 441–448.
- STOC-2014-AwasthiBL #learning #linear #locality #power of
- The power of localization for efficiently learning linear separators with noise (PA, MFB, PML), pp. 449–458.
- STOC-2014-DekelDKP
- Bandits with switching costs: T2/3 regret (OD, JD, TK, YP), pp. 459–467.
- STOC-2014-Christiano #learning #online #programming
- Online local learning via semidefinite programming (PC), pp. 468–474.
- STOC-2014-SahaiW #encryption #how #obfuscation
- How to use indistinguishability obfuscation: deniable encryption, and more (AS, BW), pp. 475–484.
- STOC-2014-KalaiRR #how #power of #proving
- How to delegate computations: the power of no-signaling proofs (YTK, RR, RDR), pp. 485–494.
- STOC-2014-GenkinIPST
- Circuits resilient to additive attacks with applications to secure computation (DG, YI, MP, AS, ET), pp. 495–504.
- STOC-2014-BitanskyCPR #on the
- On the existence of extractable one-way functions (NB, RC, OP, AR), pp. 505–514.
- STOC-2014-GoyalOSV #black box
- Black-box non-black-box zero knowledge (VG, RO, AS, IV), pp. 515–524.
- STOC-2014-GargMV #algorithm #equilibrium
- Dichotomies in equilibrium computation, and complementary pivot algorithms for a new class of non-separable utility functions (JG, RM, VVV), pp. 525–534.
- STOC-2014-Babichenko #approximate #complexity #nash #query
- Query complexity of approximate nash equilibria (YB), pp. 535–544.
- STOC-2014-Mehta #constant #game studies #rank
- Constant rank bimatrix games are PPAD-hard (RM), pp. 545–554.
- STOC-2014-AgarwalS #algorithm #approximate #geometry #metric
- Approximation algorithms for bipartite matching with metric and geometric costs (PKA, RS), pp. 555–564.
- STOC-2014-Nanongkai #algorithm #approximate #distributed
- Distributed approximation algorithms for weighted shortest paths (DN), pp. 565–573.
- STOC-2014-AndoniNOY #algorithm #geometry #graph #parallel #problem
- Parallel algorithms for geometric graph problems (AA, AN, KO, GY), pp. 574–583.
- STOC-2014-GoyalVX #composition #fourier #robust
- Fourier PCA and robust tensor decomposition (NG, SV, YX), pp. 584–593.
- STOC-2014-BhaskaraCMV #analysis
- Smoothed analysis of tensor decompositions (AB, MC, AM, AV), pp. 594–603.
- STOC-2014-ChanDSS #approximate #estimation #performance #polynomial
- Efficient density estimation via piecewise polynomial approximation (SoC, ID, RAS, XS), pp. 604–613.
- STOC-2014-GuruswamiHHSV
- Super-polylogarithmic hypergraph coloring hardness via low-degree long codes (VG, PH, JH, SS, GV), pp. 614–623.
- STOC-2014-DinurS #approach #parallel
- Analytical approach to parallel repetition (ID, DS), pp. 624–633.
- STOC-2014-KhotTW #approximate
- A characterization of strong approximation resistance (SK, MT, PW), pp. 634–643.
- STOC-2014-Vegh #algorithm #polynomial
- A strongly polynomial algorithm for generalized flow maximization (LAV), pp. 644–653.
- STOC-2014-Chechik #approximate #constant #distance #query
- Approximate distance oracles with constant query time (SC), pp. 654–663.
- STOC-2014-Williams14a #complexity #performance
- Faster all-pairs shortest paths via circuit complexity (RW), pp. 664–673.
- STOC-2014-HenzingerKN #algorithm #graph #reachability
- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs (MH, SK, DN), pp. 674–683.
- STOC-2014-Goodrich #algorithm #sorting
- Zig-zag sort: a simple deterministic data-oblivious sorting algorithm running in O(n log n) time (MTG), pp. 684–693.
- STOC-2014-Massoulie #community #detection
- Community detection thresholds and the weak Ramanujan property (LM), pp. 694–703.
- STOC-2014-MendesTH #distributed
- Distributed computability in Byzantine asynchronous systems (HM, CT, MH), pp. 704–713.
- STOC-2014-AlistarhCS #algorithm #concurrent #question
- Are lock-free concurrent algorithms practically wait-free? (DA, KCH, NS), pp. 714–723.
- STOC-2014-SharmaV #multi
- Multiway cut, pairwise realizable distributions, and descending thresholds (AS, JV), pp. 724–733.
- STOC-2014-KrishnaswamyNPS #approximate #clustering #design #energy #network #performance
- Cluster before you hallucinate: approximating node-capacitated network design and energy efficient routing (RK, VN, KP, CS), pp. 734–743.
- STOC-2014-FriggstadS #algorithm #approximate #bound
- Approximation algorithms for regret-bounded vehicle routing and applications to distance-constrained vehicle routing (ZF, CS), pp. 744–753.
- STOC-2014-EneV #algorithm #approximate #bound #design #network #problem #requirements
- Improved approximation algorithms for degree-bounded network design problems with node connectivity requirements (AE, AV), pp. 754–763.
- STOC-2014-RudraW
- Every list-decodable code for high noise has abundant near-optimal rate puncturings (AR, MW), pp. 764–773.
- STOC-2014-AggarwalDL #combinator
- Non-malleable codes from additive combinatorics (DA, YD, SL), pp. 774–783.
- STOC-2014-DvirSW #polynomial
- Breaking the quadratic barrier for 3-LCC’s over the reals (ZD, SS, AW), pp. 784–793.
- STOC-2014-GhaffariHS #adaptation #fault #interactive
- Optimal error rates for interactive coding I: adaptivity and other settings (MG, BH, MS), pp. 794–803.
- STOC-2014-Coja-Oghlan #satisfiability
- The asymptotic k-SAT threshold (ACO), pp. 804–813.
- STOC-2014-DingSS #random #satisfiability
- Satisfiability threshold for random regular NAE-SAT (JD, AS, NS), pp. 814–822.
- STOC-2014-GalanisSV
- Inapproximability for antiferromagnetic spin systems in the tree non-uniqueness region (AG, DS, EV), pp. 823–831.
- STOC-2014-DeS #approximate #performance #polynomial
- Efficient deterministic approximate counting for low-degree polynomial threshold functions (AD, RAS), pp. 832–841.
- STOC-2014-Lovett #bound #communication #rank
- Communication is bounded by root of rank (SL), pp. 842–846.
- STOC-2014-GoosP #bound #communication
- Communication lower bounds via critical block sensitivity (MG, TP), pp. 847–856.
- STOC-2014-BuhrmanCKLS #memory management
- Computing with a full memory: catalytic space (HB, RC, MK, BL, FS), pp. 857–866.
- STOC-2014-ForbesSS #algebra #branch #multi #order #set #source code
- Hitting sets for multilinear read-once algebraic branching programs, in any order (MAF, RS, AS), pp. 867–875.

15 ×#algorithm

12 ×#approximate

12 ×#bound

6 ×#complexity

6 ×#graph

6 ×#linear

6 ×#performance

5 ×#constant

5 ×#polynomial

4 ×#composition

12 ×#approximate

12 ×#bound

6 ×#complexity

6 ×#graph

6 ×#linear

6 ×#performance

5 ×#constant

5 ×#polynomial

4 ×#composition