170 citations · 876 across the 146 of their papers we have counts for
23 papers · 1 filter
Frequency Estimation with One-Sided Error
Piotr Indyk, Shyam Narayanan, David P. Woodruff
Frequency estimation is one of the most fundamental problems in streaming algorithms. Given a stream of elements from some universe , the goal is to compute,…
Active Linear Regression for Norms and Beyond
Cameron Musco, Christopher Musco, David P. Woodruff +1
We study active sampling algorithms for linear regression, which aim to query only a few entries of a target vector and output a near minimizer to $\min_{x\in\mat…
Improved Algorithms for Low Rank Approximation from Sparsity
David P. Woodruff, Taisuke Yasuda
We overcome two major bottlenecks in the study of low rank approximation by assuming the low rank factors themselves are sparse. Specifically, (1) for low rank approximation with s…
Optimal Sketching for Trace Estimation
Shuli Jiang, Hai Pham, David P. Woodruff +2
Matrix trace estimation is ubiquitous in machine learning applications and has traditionally relied on Hutchinson's method, which requires matrix-vector product…
Learning-Augmented -means Clustering
Jon C. Ergun, Zhili Feng, Sandeep Silwal +2
-means clustering is a well-studied problem due to its wide applicability. Unfortunately, there exist strong theoretical limits on the performance of any algorithm for the -m…
Truly Perfect Samplers for Data Streams and Sliding Windows
Rajesh Jayaram, David P. Woodruff, Samson Zhou
In the -sampling problem, the goal is to output an index of a vector , such that for all coordinates , \[\textbf{Pr}[i=j] = (1 \pm ε) \frac{G(f…