## Rocco A. Servedio, Ronitt Rubinfeld

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

STOC, 2015.

@proceedings{STOC-2015, acmid = "2746539", address = "Portland, Oregon, USA", editor = "Rocco A. Servedio and Ronitt Rubinfeld", isbn = "978-1-4503-3536-2", publisher = "{ACM}", title = "{Proceedings of the 47th Annual ACM Symposium on Theory of Computing}", year = 2015, }

### Contents (93 items)

- STOC-2015-Chechik #approximate #bound #distance
- Approximate Distance Oracles with Improved Bounds (SC), pp. 1–10.
- STOC-2015-LackiOPSZ #algorithm #distance #performance #power of
- The Power of Dynamic Distance Oracles: Efficient Dynamic Algorithms for the Steiner Tree (JL, JO, MP, PS, AZ), pp. 11–20.
- STOC-2015-HenzingerKNS #multi #online #problem
- Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture (MH, SK, DN, TS), pp. 21–30.
- STOC-2015-ChanL #clustering #combinator #integer
- Clustered Integer 3SUM via Additive Combinatorics (TMC, ML), pp. 31–40.
- STOC-2015-AbboudWY
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture (AA, VVW, HY), pp. 41–50.
- STOC-2015-BackursI #distance #edit distance
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false) (AB, PI), pp. 51–58.
- STOC-2015-DingSS #proving #satisfiability #scalability
- Proof of the Satisfiability Conjecture for Large k (JD, AS, NS), pp. 59–68.
- STOC-2015-MosselNS #consistency
- Consistency Thresholds for the Planted Bisection Model (EM, JN, AS), pp. 69–75.
- STOC-2015-FeldmanPV #complexity #on the #problem #random #satisfiability
- On the Complexity of Random Satisfiability Problems with Planted Solutions (VF, WP, SV), pp. 77–86.
- STOC-2015-MekaPW #bound #clique
- Sum-of-squares Lower Bounds for Planted Clique (RM, AP, AW), pp. 87–96.
- STOC-2015-BarakCK #bound #independence
- Sum of Squares Lower Bounds from Pairwise Independence (BB, SOC, PKK), pp. 97–106.
- STOC-2015-BraunPZ #combinator #problem
- Inapproximability of Combinatorial Problems via Small LPs and SDPs (GB, SP, DZ), pp. 107–116.
- STOC-2015-DworkFHPRR #adaptation #data analysis #statistics
- Preserving Statistical Validity in Adaptive Data Analysis (CD, VF, MH, TP, OR, ALR), pp. 117–126.
- STOC-2015-BassilyS #performance #protocol
- Local, Private, Efficient Protocols for Succinct Histograms (RB, ADS), pp. 127–135.
- STOC-2015-LovettZ #difference
- Improved Noisy Population Recovery, and Reverse Bonami-Beckner Inequality for Sparse Functions (SL, JZ), pp. 137–142.
- STOC-2015-BarakKS #composition #learning #taxonomy
- Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method (BB, JAK, DS), pp. 143–151.
- STOC-2015-MirrokniZ #composition #distributed #random
- Randomized Composable Core-sets for Distributed Submodular Maximization (VSM, MZ), pp. 153–162.
- STOC-2015-CohenEMMP #approximate #clustering #rank #reduction
- Dimensionality Reduction for k-Means Clustering and Low Rank Approximation (MBC, SE, CM, CM, MP), pp. 163–172.
- STOC-2015-BhattacharyaHNT #algorithm #maintenance
- Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams (SB, MH, DN, CET), pp. 173–182.
- STOC-2015-CohenP
- Lp Row Sampling by Lewis Weights (MBC, RP), pp. 183–192.
- STOC-2015-BansalGG #graph #independence #on the #set
- On the Lovász Theta function for Independent Sets in Sparse Graphs (NB, AG, GG), pp. 193–200.
- STOC-2015-FearnleyS #complexity
- The Complexity of the Simplex Method (JF, RS), pp. 201–208.
- STOC-2015-HansenZ #algorithm
- An Improved Version of the Random-Facet Pivoting Rule for the Simplex Algorithm (TDH, UZ), pp. 209–218.
- STOC-2015-ChawlaMSY #algorithm #clustering #graph
- Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs (SC, KM, TS, GY), pp. 219–228.
- STOC-2015-ZhuO #convergence #performance
- Nearly-Linear Time Positive LP Solver with Faster Convergence Rate (ZAZ, LO), pp. 229–236.
- STOC-2015-ZhuLO #matrix #multi
- Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates (ZAZ, ZL, LO), pp. 237–245.
- STOC-2015-KothariM #generative #pseudo
- Almost Optimal Pseudorandom Generators for Spherical Caps: Extended Abstract (PKK, RM), pp. 247–256.
- STOC-2015-GoosLM0Z
- Rectangles Are Nonnegative Juntas (MG, SL, RM, TW, DZ), pp. 257–266.
- STOC-2015-DinurHK #composition #fault #query
- Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition (ID, PH, GK), pp. 267–276.
- STOC-2015-BhowmickL
- The List Decoding Radius of Reed-Muller Codes over Small Fields (AB, SL), pp. 277–285.
- STOC-2015-ChenJL #capacity #online
- A Characterization of the Capacity of Online (causal) Binary Channels (ZC, SJ, ML), pp. 287–296.
- STOC-2015-AbbeSW #fault #random
- Reed-Muller Codes for Random Erasures and Errors (EA, AS, AW), pp. 297–306.
- STOC-2015-AaronsonA #named #problem #quantum
- Forrelation: A Problem that Optimally Separates Quantum from Classical Computing (SA, AA), pp. 307–316.
- STOC-2015-Touchette #complexity #quantum
- Quantum Information Complexity (DT), pp. 317–326.
- STOC-2015-BaconFHS #quantum
- Sparse Quantum Codes from Quantum Circuits (DB, STF, AWH, JS), pp. 327–334.
- STOC-2015-BravermanG #game studies #parallel
- Small Value Parallel Repetition for General Games (MB, AG), pp. 335–340.
- STOC-2015-BravermanW #interactive
- An Interactive Information Odometer and Applications (MB, OW), pp. 341–350.
- STOC-2015-GowersV #communication #complexity
- The communication complexity of interleaved group products (TG, EV), pp. 351–360.
- STOC-2015-Barman #approximate #nash #theorem
- Approximating Nash Equilibria and Dense Bipartite Subgraphs via an Approximate Version of Caratheodory’s Theorem (SB), pp. 361–369.
- STOC-2015-ColeG #approximate #nash #social
- Approximating the Nash Social Welfare with Indivisible Items (RC, VG), pp. 371–380.
- STOC-2015-ChenDO #complexity #game studies #nash #on the
- On the Complexity of Nash Equilibria in Anonymous Games (XC, DD, AO), pp. 381–390.
- STOC-2015-Lee #graph
- Hardness of Graph Pricing Through Generalized Max-Dicut (EL), pp. 391–399.
- STOC-2015-DanielySS
- Inapproximability of Truthful Mechanisms via Generalizations of the VC Dimension (AD, MS, GS), pp. 401–408.
- STOC-2015-Rubinstein #equilibrium #nash
- Inapproximability of Nash Equilibrium (AR), pp. 409–418.
- STOC-2015-KoppulaLW #bound #memory management #obfuscation #turing machine
- Indistinguishability Obfuscation for Turing Machines with Unbounded Memory (VK, ABL, BW), pp. 419–428.
- STOC-2015-CanettiH0V #obfuscation #ram #source code
- Succinct Garbling and Indistinguishability Obfuscation for RAM Programs (RC, JH, AJ, VV), pp. 429–437.
- STOC-2015-BitanskyGLPT #encoding #random
- Succinct Randomized Encodings and their Applications (NB, SG, HL, RP, ST), pp. 439–448.
- STOC-2015-GargLOS #ram
- Garbled RAM From One-Way Functions (SG, SL, RO, AS), pp. 449–458.
- STOC-2015-AggarwalDKO #reduction
- Non-malleable Reductions and Applications (DA, YD, TK, MO), pp. 459–468.
- STOC-2015-GorbunovVW #standard
- Leveled Fully Homomorphic Signatures from Standard Lattices (SG, VV, DW), pp. 469–477.
- STOC-2015-AndoniKR #sketching
- Sketching and Embedding are Equivalent for Norms (AA, RK, IPR), pp. 479–488.
- STOC-2015-ElkinFN #metric
- Prioritized Metric Structures and Embedding (ME, AF, ON), pp. 489–498.
- STOC-2015-BourgainDN #formal method #reduction #towards
- Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean Space (JB, SD, JN), pp. 499–508.
- STOC-2015-AbdullahV #bound #difference
- A Directed Isoperimetric Inequality with application to Bregman Near Neighbor Lower Bounds (AA, SV), pp. 509–518.
- STOC-2015-ChenDST #adaptation #query #testing
- Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries (XC, AD, RAS, LYT), pp. 519–528.
- STOC-2015-ODonnellW #quantum #testing
- Quantum Spectrum Testing (RO, JW), pp. 529–538.
- STOC-2015-CousinsV #algorithm
- Bypassing KLS: Gaussian Cooling and an O^*(n3) Volume Algorithm (BC, SV), pp. 539–548.
- STOC-2015-LiuL #bound
- FPTAS for #BIS with Degree Bounds on One Side (JL, PL), pp. 549–556.
- STOC-2015-GanorKR #communication #exponential
- Exponential Separation of Information and Communication for Boolean Functions (AG, GK, RR), pp. 557–566.
- STOC-2015-LeeRS #bound #programming
- Lower Bounds on the Size of Semidefinite Programming Relaxations (JRL, PR, DS), pp. 567–576.
- STOC-2015-DvirG #communication
- 2-Server PIR with Sub-Polynomial Communication (ZD, SG), pp. 577–584.
- STOC-2015-AmbainisFG #matrix #multi #performance
- Fast Matrix Multiplication: Limitations of the Coppersmith-Winograd Method (AA, YF, FLG), pp. 585–593.
- STOC-2015-AlwenS #complexity #graph #parallel
- High Parallel Complexity Graphs and Memory-Hard Functions (JA, VS), pp. 595–603.
- STOC-2015-AbrahamD #complexity #polynomial
- Byzantine Agreement with Optimal Early Stopping, Optimal Resilience and Polynomial Complexity (IA, DD), pp. 605–614.
- STOC-2015-GiakkoupisHHW
- Test-and-Set in Optimal Space (GG, MH, LH, PW), pp. 615–623.
- STOC-2015-AlstrupKTZ #graph
- Adjacency Labeling Schemes and Induced-Universal Graphs (SA, HK, MT, UZ), pp. 625–634.
- STOC-2015-HalldorssonT #graph #how #question
- How Well Can Graphs Represent Wireless Interference? (MMH, TT), pp. 635–644.
- STOC-2015-Chuzhoy #grid #theorem
- Excluded Grid Theorem: Improved and Simplified (JC), pp. 645–654.
- STOC-2015-KawarabayashiK #grid #theorem
- The Directed Grid Theorem (KiK, SK), pp. 655–664.
- STOC-2015-KawarabayashiT #graph
- Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time (KiK, MT), pp. 665–674.
- STOC-2015-KawarabayashiS #approximate #graph
- Beyond the Euler Characteristic: Approximating the Genus of General Graphs (KiK, AS), pp. 675–682.
- STOC-2015-GroheS
- Computing with Tangles (MG, PS), pp. 683–692.
- STOC-2015-SunW #canonical #performance
- Faster Canonical Forms for Primitive Coherent Configurations: Extended Abstract (XS, JW), pp. 693–702.
- STOC-2015-Czumaj #network #permutation #random #using
- Random Permutations using Switching Networks (AC), pp. 703–712.
- STOC-2015-Louis #algorithm #approximate #markov
- Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms (AL), pp. 713–722.
- STOC-2015-CzumajPS #clustering #graph #testing
- Testing Cluster Structure of Graphs (AC, PP, CS), pp. 723–732.
- STOC-2015-AggarwalDRS #problem #using
- Solving the Shortest Vector Problem in 2n Time Using Discrete Gaussian Sampling: Extended Abstract (DA, DD, OR, NSD), pp. 733–742.
- STOC-2015-LiRSS #learning #statistics
- Learning Arbitrary Statistical Mixtures of Discrete Distributions (JL, YR, LJS, CS), pp. 743–752.
- STOC-2015-HardtP #bound #learning
- Tight Bounds for Learning a Mixture of Two Gaussians (MH, EP), pp. 753–760.
- STOC-2015-GeHK #learning
- Learning Mixtures of Gaussians in High Dimensions (RG, QH, SMK), pp. 761–770.
- STOC-2015-Bresler #graph #learning #modelling
- Efficiently Learning Ising Models on Arbitrary Graphs (GB), pp. 771–782.
- STOC-2015-MulzerNSS #approximate #nearest neighbour
- Approximate k-flat Nearest Neighbor Search (WM, HLN, PS, YS), pp. 783–792.
- STOC-2015-AndoniR #approximate
- Optimal Data-Dependent Hashing for Approximate Near Neighbors (AA, IR), pp. 793–801.
- STOC-2015-LarsenNN #adaptation #algorithm #bound #streaming
- Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms (KGL, JN, HLN), pp. 803–812.
- STOC-2015-ChristianiPT #independence
- From Independence to Expansion and Back Again (TC, RP, MT), pp. 813–820.
- STOC-2015-Moitra #matrix
- Super-resolution, Extremal Functions and the Condition Number of Vandermonde Matrices (AM), pp. 821–830.
- STOC-2015-SchulmanS #algorithm #analysis #matrix
- Analysis of a Classical Matrix Preconditioning Algorithm (LJS, AS), pp. 831–840.
- STOC-2015-FoxKM #approximate #polynomial
- A Polynomial-time Bicriteria Approximation Scheme for Planar Bisection (KF, PNK, SM), pp. 841–850.
- STOC-2015-BansalK
- Minimizing Flow-Time on Unrelated Machines (NB, JK), pp. 851–860.
- STOC-2015-Nikolov #problem #random
- Randomized Rounding for the Largest Simplex Problem (AN), pp. 861–870.
- STOC-2015-Gupta0 #algorithm
- Greedy Algorithms for Steiner Forest (AG, AK), pp. 871–878.
- STOC-2015-KesselheimKN #order #problem
- Secretary Problems with Non-Uniform Arrival Order (TK, RDK, RN), pp. 879–888.
- STOC-2015-KorulaMZ #online #order #random
- Online Submodular Welfare Maximization: Greedy Beats 1/2 in Random Order (NK, VSM, MZ), pp. 889–898.

10 ×#graph

9 ×#algorithm

9 ×#approximate

9 ×#bound

7 ×#complexity

7 ×#problem

7 ×#random

5 ×#learning

5 ×#performance

4 ×#clustering

9 ×#algorithm

9 ×#approximate

9 ×#bound

7 ×#complexity

7 ×#problem

7 ×#random

5 ×#learning

5 ×#performance

4 ×#clustering