4 citations · 18 across the 38 of their papers we have counts for
8 papers · 1 filter
Perfect Sampling with Polylogarithmic Update Time
William Swartworth, David P. Woodruff, Samson Zhou
Perfect sampling in a stream was introduced by Jayaram and Woodruff (FOCS 2018) as a streaming primitive which, given turnstile updates to a vector $x \in \{-\text{poly}(n),…
Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams
Vincent Cohen-Addad, David P. Woodruff, Shenghao Xie +1
We study the problem of graph and hypergraph sparsification in insertion-only data streams. The input is a hypergraph with nodes, hyperedges, and rank , an…
On Fine-Grained Distinct Element Estimation
Ilias Diakonikolas, Daniel M. Kane, Jasper C. H. Lee +3
We study the problem of distributed distinct element estimation, where servers each receive a subset of a universe and aim to compute a -approximation to…
Private Training & Data Generation by Clustering Embeddings
Felix Zhou, Samson Zhou, Vahab Mirrokni +2
Deep neural networks often use large, high-quality datasets to achieve high performance on many machine learning tasks. When training involves potentially sensitive data, this proc…
Fast, Space-Optimal Streaming Algorithms for Clustering and Subspace Embeddings
Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff +1
We show that both clustering and subspace embeddings can be performed in the streaming model with the same asymptotic efficiency as in the central/offline setting. For -clu…
Perfect Sampling in Turnstile Streams Beyond Small Moments
David P. Woodruff, Shenghao Xie, Samson Zhou
Given a vector induced by a turnstile stream , a non-negative function , a perfect -sampler outputs an index with proba…
Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness
Elena Gribelyuk, Honghao Lin, David P. Woodruff +2
We introduce a novel technique for ``lifting'' dimension lower bounds for linear sketches in the real-valued setting to dimension lower bounds for linear sketches with polynomially…
Fair Clustering in the Sliding Window Model
Vincent Cohen-Addad, Shaofeng H. -C. Jiang, Qiaoyuan Yang +2
We study streaming algorithms for proportionally fair clustering, a notion originally suggested by Chierichetti et. al. (2017), in the sliding window model. We show that although t…