BibSLEIGH — Proceedings of the 46th Annual ACM Symposium on Theory of Computing

David B. Shmoys
Proceedings of the 46th Annual ACM Symposium on Theory of Computing
STOC, 2014.

TCS

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

David B. ShmoysProceedings of the 46th Annual ACM Symposium on Theory of ComputingSTOC, 2014.

Contents (91 items)

David B. Shmoys
Proceedings of the 46th Annual ACM Symposium on Theory of Computing
STOC, 2014.