4 citations · 6 across the 21 of their papers we have counts for
18 papers · 1 filter
Distributed Algorithms for Euclidean Clustering
Vincent Cohen-Addad, Liudeng Wang, David P. Woodruff +1
We study the problem of constructing -coresets for Euclidean -clustering in the distributed setting, where data points are partitioned across sites.…
Learning-Augmented Moment Estimation on Time-Decay Models
Soham Nagawanshi, Shalini Panthangi, Chen Wang +2
Motivated by the prevalence and success of machine learning, a line of recent work has studied learning-augmented algorithms in the streaming model. These results have shown that f…
Consistent Low-Rank Approximation
David P. Woodruff, Samson Zhou
We introduce and study the problem of consistent low-rank approximation, in which rows of an input matrix arrive sequentially and the goal is…
Adversarial Robustness on Insertion-Deletion Streams
Elena Gribelyuk, Honghao Lin, David P. Woodruff +2
We study adversarially robust algorithms for insertion-deletion (turnstile) streams, where future updates may depend on past algorithm outputs. While robust algorithms exist for in…
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…