From the 1 of 18 linked papers with an AI index.
18 papers
The Adversarial Robustness of Sketching and Streaming Algorithms
David P. Woodruff, Samson Zhou
The paper surveys recent work on making sketching and streaming algorithms robust against adaptive (adversarial) inputs, covering techniques based on differential privacy, cryptogr…
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…
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…
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.…