4 citations · 18 across the 38 of their papers we have counts for
4 papers · 1 filter
On Socially Fair Low-Rank Approximation and Column Subset Selection
Zhao Song, Ali Vakilian, David P. Woodruff +1
Low-rank approximation and column subset selection are two fundamental and related problems that are applied across a wealth of machine learning applications. In this paper, we stu…
Adversarially Robust Dense-Sparse Tradeoffs via Heavy-Hitters
David P. Woodruff, Samson Zhou
In the adversarial streaming model, the input is a sequence of adaptive updates that defines an underlying dataset and the goal is to approximate, collect, or compute some statisti…
A Strong Separation for Adversarially Robust Estimation for Linear Sketches
Elena Gribelyuk, Honghao Lin, David P. Woodruff +2
The majority of streaming problems are defined and analyzed in a static setting, where the data stream is any worst-case sequence of insertions and deletions that is fixed in advan…
Streaming Algorithms with Few State Changes
Rajesh Jayaram, David P. Woodruff, Samson Zhou
In this paper, we study streaming algorithms that minimize the number of changes made to their internal state (i.e., memory contents). While the design of streaming algorithms typi…