4 citations · 18 across the 38 of their papers we have counts for
6 papers · 1 filter
Near-Optimal -Clustering in the Sliding Window Model
David P. Woodruff, Peilin Zhong, Samson Zhou
Clustering is an important technique for identifying structural information in large-scale data analysis, where the underlying dataset may be too large to store. In many applicatio…
Streaming Euclidean -median and -means with Space
Vincent Cohen-Addad, David P. Woodruff, Samson Zhou
We consider the classic Euclidean -median and -means objective on data streams, where the goal is to provide a -approximation to the optimal -median or $k…
Fast -Approximation Algorithms for Binary Matrix Factorization
Ameya Velingker, Maximilian Vötsch, David P. Woodruff +1
We introduce efficient -approximation algorithms for the binary matrix factorization (BMF) problem, where the inputs are a matrix $\mathbf{A}\in\{0,1\}^{n\times d}…
Robust Algorithms on Adaptive Inputs from Bounded Adversaries
Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff +3
We study dynamic algorithms robust to adaptive input generated from sources with bounded capabilities, such as sparsity or limited interaction. For example, we consider robust line…
Streaming Algorithms for Learning with Experts: Deterministic Versus Robust
David P. Woodruff, Fred Zhang, Samson Zhou
In the online learning with experts problem, an algorithm must make a prediction about an outcome on each of days (or times), given a set of experts who make predictions on…
On Differential Privacy and Adaptive Data Analysis with Bounded Space
Itai Dinur, Uri Stemmer, David P. Woodruff +1
We study the space complexity of the two related fields of differential privacy and adaptive data analysis. Specifically, (1) Under standard cryptographic assumptions, we show that…