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

Dan Boneh, Tim Roughgarden, Joan Feigenbaum
Proceedings of the 45th Annual ACM Symposium on Theory of Computing
STOC, 2013.

TCS

@proceedings{STOC-2013,
	acmid         = "2488608",
	address       = "Palo Alto, California, USA",
	editor        = "Dan Boneh and Tim Roughgarden and Joan Feigenbaum",
	isbn          = "978-1-4503-2029-0",
	publisher     = "{ACM}",
	title         = "{Proceedings of the 45th Annual ACM Symposium on Theory of Computing}",
	year          = 2013,
}

Contents (100 items)

STOC-2013-KaneM: A PRG for lipschitz functions of polynomials with applications to sparsest cut (DMK, RM), pp. 1–10.
STOC-2013-KwokLLGT #algorithm #analysis #clustering #difference #higher-order: Improved Cheeger’s inequality: analysis of spectral partitioning algorithms through higher order spectral gap (TCK, LCL, YTL, SOG, LT), pp. 11–20.
STOC-2013-Williams #proving: Natural proofs versus derandomization (RW), pp. 21–30.
STOC-2013-BeiCZ #complexity #fault #on the: On the complexity of trial and error (XB, NC, SZ), pp. 31–40.
STOC-2013-BhawalkarGM #game studies: Coevolutionary opinion formation games (KB, SG, KM), pp. 41–50.
STOC-2013-ChawlaHMS #independence #scheduling: Prior-independent mechanisms for scheduling (SC, JDH, DLM, BS), pp. 51–60.
STOC-2013-FeldmanGL #combinator #equilibrium: Combinatorial walrasian equilibrium (MF, NG, BL), pp. 61–70.
STOC-2013-NaorRV #commutative #difference #performance: Efficient rounding for the noncommutative grothendieck inequality (AN, OR, TV), pp. 71–80.
STOC-2013-ClarksonW #approximate #rank: Low rank approximation and regression in input sparsity time (KLC, DPW), pp. 81–90.
STOC-2013-MengM #linear #robust: Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression (XM, MWM), pp. 91–100.
STOC-2013-NelsonN #bound: Sparsity lower bounds for dimensionality reducing maps (JN, HLN), pp. 101–110.
STOC-2013-BitanskyCCT #composition #recursion: Recursive composition and bootstrapping for SNARKS and proof-carrying data (NB, RC, AC, ET), pp. 111–120.
STOC-2013-HardtW #adaptation #how #linear #question #robust #sketching: How robust are linear sketches to adaptive inputs? (MH, DPW), pp. 121–130.
STOC-2013-BohmGJ #automaton #equivalence: Equivalence of deterministic one-counter automata is NL-complete (SB, SG, PJ), pp. 131–140.
STOC-2013-BurgisserI #bound #complexity #geometry: Explicit lower bounds via geometric complexity theory (PB, CI), pp. 141–150.
STOC-2013-BravermanGPW #communication: From information to exact communication (MB, AG, DP, OW), pp. 151–160.
STOC-2013-BravermanM #approach #complexity: An information complexity approach to extended formulations (MB, AM), pp. 161–170.
STOC-2013-KomargodskiR #bound: Average-case lower bounds for formula size (IK, RR), pp. 171–180.
STOC-2013-ChenPY #complexity: The complexity of non-monotone markets (XC, DP, MY), pp. 181–190.
STOC-2013-CheungCD: Tatonnement beyond gross substitutes?: gradient descent to the rescue (YKC, RC, NRD), pp. 191–200.
STOC-2013-FeldmanFGL #performance: Simultaneous auctions are (almost) efficient (MF, HF, NG, BL), pp. 201–210.
STOC-2013-SyrgkanisT #composition #performance: Composable and efficient mechanisms (VS, ÉT), pp. 211–220.
STOC-2013-Goyal #concurrent #simulation: Non-black-box simulation in the fully concurrent setting (VG), pp. 221–230.
STOC-2013-ChungPS #security #simulation: Non-black-box simulation from one-way functions and applications to resettable security (KMC, RP, KS), pp. 231–240.
STOC-2013-BitanskyP #approximate #encryption #obfuscation #on the: On the impossibility of approximate obfuscation and applications to resettable cryptography (NB, OP), pp. 241–250.
STOC-2013-MilesV: Shielding circuits with groups (EM, EV), pp. 251–260.
STOC-2013-BabaiW #canonical #design: Quasipolynomial-time canonical form for steiner designs (LB, JW), pp. 261–270.
STOC-2013-ChenST #design #morphism #multi #testing: Multi-stage design for quasipolynomial-time isomorphism testing of steiner 2-systems (XC, XS, SHT), pp. 271–280.
STOC-2013-GuptaTW #algorithm #bound #graph: Sparsest cut on bounded treewidth graphs: algorithms and hardness results (AG, KT, DW), pp. 281–290.
STOC-2013-ChekuriC #graph: Large-treewidth graph decompositions and applications (CC, JC), pp. 291–300.
STOC-2013-CyganKN #performance: Fast hamiltonicity checking via bases of perfect matchings (MC, SK, JN), pp. 301–310.
STOC-2013-KeevashKM #polynomial: Polynomial-time perfect matchings in dense hypergraphs (PK, FK, RM), pp. 311–320.
STOC-2013-AgrawalSS: Quasi-polynomial hitting-set for set-depth-Δ formulas (MA, CS, NS), pp. 321–330.
STOC-2013-HardtR #analysis #worst-case: Beyond worst-case analysis in private singular vector computation (MH, AR), pp. 331–340.
STOC-2013-HsuRU #difference #equilibrium #privacy: Differential privacy for the analyst via private equilibrium computation (JH, AR, JU), pp. 341–350.
STOC-2013-NikolovTZ #approximate #difference #geometry #privacy: The geometry of differential privacy: the sparse and approximate cases (AN, KT, LZ), pp. 351–360.
STOC-2013-Ullman #difference #privacy #query: Answering n{2+o(1)} counting queries with differential privacy is hard (JU), pp. 361–370.
STOC-2013-Thorup #independence #set #similarity: Bottom-k and priority sampling, set similarity and subset sums with minimal independence (MT), pp. 371–380.
STOC-2013-LenzenP #performance #using: Fast routing table construction using small messages: extended abstract (CL, BPS), pp. 381–390.
STOC-2013-MendesH #approximate #multi: Multidimensional approximate agreement in Byzantine asynchronous systems (HM, MH), pp. 391–400.
STOC-2013-KingS #polynomial: Byzantine agreement in polynomial expected time: [extended abstract] (VK, JS), pp. 401–410.
STOC-2013-ChakrabartyS: A o(n) monotonicity tester for boolean functions over the hypercube (DC, CS), pp. 411–418.
STOC-2013-ChakrabartyS13a #bound #testing: Optimal bounds for monotonicity and lipschitz testing over hypercubes and hypergrids (DC, CS), pp. 419–428.
STOC-2013-BhattacharyyaFHHL #invariant: Every locally characterized affine-invariant property is testable (AB, EF, HH, PH, SL), pp. 429–436.
STOC-2013-KawarabayashiY #graph #testing: Testing subdivision-freeness: property testing meets structural graph theory (KiK, YY), pp. 437–446.
STOC-2013-Chan #approximate #independence: Approximation resistance from pairwise independent subgroups (SOC), pp. 447–456.
STOC-2013-Huang #approximate #satisfiability: Approximation resistance on satisfiable instances for predicates with few accepting inputs (SH), pp. 457–466.
STOC-2013-GargGSW #encryption: Witness encryption and its applications (SG, CG, AS, BW), pp. 467–476.
STOC-2013-DeMN: Majority is stablest: discrete and SoS (AD, EM, JN), pp. 477–486.
STOC-2013-BeckI: Strong ETH holds for regular resolution (CB, RI), pp. 487–494.
STOC-2013-LeeMM #theorem: A node-capacitated okamura-seymour theorem (JRL, MM, MM), pp. 495–504.
STOC-2013-KleinMS #graph #linear #recursion: Structured recursive separator decompositions for planar graphs in linear time (PNK, SM, CS), pp. 505–514.
STOC-2013-RodittyW #algorithm #approximate #graph #performance: Fast approximation algorithms for the diameter and radius of sparse graphs (LR, VVW), pp. 515–524.
STOC-2013-GuGK #maintenance #online #power of: The power of deferral: maintaining a constant-competitive steiner tree online (AG, AG, AK), pp. 525–534.
STOC-2013-BuchbinderNS #clustering #exponential #multi #problem: Simplex partitioning via exponential clocks and the multiway cut problem (NB, JN, RS), pp. 535–544.
STOC-2013-GorbunovVW #encryption: Attribute-based encryption for circuits (SG, VV, HW), pp. 545–554.
STOC-2013-GoldwasserKPVZ #encryption #functional #reuse: Reusable garbled circuits and succinct functional encryption (SG, YTK, RAP, VV, NZ), pp. 555–564.
STOC-2013-KalaiRR #bound: Delegation for bounded space (YTK, RR, RDR), pp. 565–574.
STOC-2013-BrakerskiLPRS #fault #learning: Classical hardness of learning with errors (ZB, AL, CP, OR, DS), pp. 575–584.
STOC-2013-Ben-SassonCGT #on the #performance #proving: On the concrete efficiency of probabilistically-checkable proofs (EBS, AC, DG, ET), pp. 585–594.
STOC-2013-CadekKMVW: Extending continuous maps: polynomiality and undecidability (MC, MK, JM, LV, UW), pp. 595–604.
STOC-2013-Har-PeledR #algorithm #distance #linear #problem: Net and prune: a linear time algorithm for euclidean distance problems (SHP, BAR), pp. 605–614.
STOC-2013-CaputoMSS #algorithm #random: Random lattice triangulations: structure and algorithms (PC, FM, AS, AS), pp. 615–624.
STOC-2013-SinclairS #complexity #theorem: Lee-Yang theorems and the complexity of computing averages (AS, PS), pp. 625–634.
STOC-2013-CaiGW: A complete dichotomy rises from the capture of vanishing signatures: extended abstract (JYC, HG, TW), pp. 635–644.
STOC-2013-ElkinS: Optimal euclidean spanners: really short, thin and lanky (ME, SS), pp. 645–654.
STOC-2013-FeldmanGRVX #algorithm #bound #clique #detection #statistics: Statistical algorithms and a lower bound for detecting planted cliques (VF, EG, LR, SV, YX), pp. 655–664.
STOC-2013-JainNS #matrix #rank #using: Low-rank matrix completion using alternating minimization (PJ, PN, SS), pp. 665–674.
STOC-2013-AlonLSV #algorithm #approximate #matrix #rank: The approximate rank of a matrix and its algorithmic applications: approximate rank (NA, TL, AS, SV), pp. 675–684.
STOC-2013-HarrisS #constraints: Constraint satisfaction, packet routing, and the lovasz local lemma (DGH, AS), pp. 685–694.
STOC-2013-ThapperZ #complexity: The complexity of finite-valued CSPs (JT, SZ), pp. 695–704.
STOC-2013-Coja-OghlanP #satisfiability: Going after the k-SAT threshold (ACO, KP), pp. 705–714.
STOC-2013-KolR #capacity #interactive: Interactive channel capacity (GK, RR), pp. 715–724.
STOC-2013-Bernstein #graph #maintenance: Maintaining shortest paths under deletions in weighted directed graphs: [extended abstract] (AB), pp. 725–734.
STOC-2013-EisenstatK #algorithm #graph #linear #multi: Linear-time algorithms for max flow and multiple-source shortest paths in unit-weight planar graphs (DE, PNK), pp. 735–744.
STOC-2013-NeimanS #algorithm: Simple deterministic algorithms for fully dynamic maximal matching (ON, SS), pp. 745–754.
STOC-2013-LeeRS #approach #using: A new approach to computing maximum flows using electrical flows (YTL, SR, NS), pp. 755–764.
STOC-2013-Orlin: Max flows in O(nm) time, or better (JBO), pp. 765–774.
STOC-2013-BringmannL: Succinct sampling from discrete distributions (KB, KGL), pp. 775–782.
STOC-2013-Li #exponential #independence: New independent source extractors with exponential improvement (XL), pp. 783–792.
STOC-2013-RothblumVW #interactive #proving #proximity #sublinear: Interactive proofs of proximity: delegating computation in sublinear time (GNR, SPV, AW), pp. 793–802.
STOC-2013-Ajtai #bound #quantifier: Lower bounds for RAMs and quantifier elimination (MA), pp. 803–812.
STOC-2013-BeckNT #calculus #polynomial #trade-off: Some trade-off results for polynomial calculus: extended abstract (CB, JN, BT), pp. 813–822.
STOC-2013-BhowmickDL #bound #product line: New bounds for matching vector families (AB, ZD, SL), pp. 823–832.
STOC-2013-Ben-SassonGKKS #algebra #geometry #product line: A new family of locally correctable codes based on degree-lifted algebraic geometry codes (EBS, AG, YK, SK, SS), pp. 833–842.
STOC-2013-GuruswamiX #algebra #bound #geometry: List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound (VG, CX), pp. 843–852.
STOC-2013-Wootters #fault #linear #on the #random #scalability: On the list decodability of random linear codes with large error rates (MW), pp. 853–860.
STOC-2013-BrandaoH #metric #quantum #theorem: Quantum de finetti theorems under local measurements with applications (FGSLB, AWH), pp. 861–870.
STOC-2013-BrandaoH13a #approximate #quantum: Product-state approximations to quantum ground states (FGSLB, AWH), pp. 871–880.
STOC-2013-Ta-Shma #matrix #quantum: Inverting well conditioned matrices in quantum logspace (ATS), pp. 881–890.
STOC-2013-Ambainis #algorithm #quantum: Superlinear advantage for exact quantum algorithms (AA), pp. 891–900.
STOC-2013-LiS #approximate #pseudo: Approximating k-median via pseudo-approximation (SL, OS), pp. 901–910.
STOC-2013-KelnerOSZ #algorithm #combinator: A simple, combinatorial algorithm for solving SDD systems in nearly-linear time (JAK, LO, AS, ZAZ), pp. 911–920.
STOC-2013-Sherstov #bound #communication #using: Communication lower bounds using directional derivatives (AAS), pp. 921–930.
STOC-2013-AndoniGMP #sketching: Homomorphic fingerprints under misalignments: sketching edit and shift distances (AA, AG, AM, EP), pp. 931–940.
STOC-2013-ChonevOW #problem: The orbit problem in higher dimensions (VC, JO, JW), pp. 941–950.
STOC-2013-AzarCG: The loss of serving in the dark (YA, IRC, IG), pp. 951–960.
STOC-2013-AzarCKS #bound #online: Tight bounds for online vector bin packing (YA, IRC, SK, FBS), pp. 961–970.
STOC-2013-LiY #approximate #combinator #optimisation #probability: Stochastic combinatorial optimization via poisson approximation (JL, WY), pp. 971–980.
STOC-2013-Miller #graph #optimisation #problem #scalability #using: Solving large optimization problems using spectral graph theory (GLM), p. 981.

Dan Boneh, Tim Roughgarden, Joan FeigenbaumProceedings of the 45th Annual ACM Symposium on Theory of ComputingSTOC, 2013.

Contents (100 items)

Dan Boneh, Tim Roughgarden, Joan Feigenbaum
Proceedings of the 45th Annual ACM Symposium on Theory of Computing
STOC, 2013.