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…
Fast White-Box Adversarial Streaming Without a Random Oracle
Ying Feng, Aayush Jain, David P. Woodruff
Recently, the question of adversarially robust streaming, where the stream is allowed to depend on the randomness of the streaming algorithm, has gained a lot of attention. In this…