4 citations · 18 across the 38 of their papers we have counts for
41 papers
High Probability Streaming Lower Bounds for Estimation
William Swartworth, David P. Woodruff, Samson Zhou
Estimating the second frequency moment () of an underlying frequency vector is a fundamental problem in the streaming model. While recent work by Braverman and Zamir [STOC 202…
The Adversarial Robustness of Sketching and Streaming Algorithms
David P. Woodruff, Samson Zhou
Sketching and streaming algorithms are vital for handling massive datasets. While classical methods guarantee correctness on fixed inputs, they often fail with adaptive inputs, whe…
Adversarial Robustness for Small Frequency Moments and a Weak Equivalence Theorem for Turnstile 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 recent work achieved a robust…
Active Learning with Low-Rank Structure for Data Selection
Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni +3
In the data selection problem, the objective is to choose a small, representative subset of data that can be used to efficiently train a machine learning model. Sener and Savarese…
Better Bounds for the Distributed Experts Problem
David P. Woodruff, Samson Zhou
In this paper, we study the distributed experts problem, where experts are distributed across servers for timesteps. The loss of each expert at each time is the $\e…
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.…