## Dan Boneh, Tim Roughgarden, Joan Feigenbaum

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

STOC, 2013.

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

12 ×#bound

11 ×#algorithm

11 ×#approximate

8 ×#graph

7 ×#performance

6 ×#complexity

6 ×#linear

5 ×#difference

5 ×#using

4 ×#encryption

11 ×#algorithm

11 ×#approximate

8 ×#graph

7 ×#performance

6 ×#complexity

6 ×#linear

5 ×#difference

5 ×#using

4 ×#encryption