170 citations · 876 across the 146 of their papers we have counts for
5 papers · 2 filters
How Robust are Linear Sketches to Adaptive Inputs?
Moritz Hardt, David P. Woodruff
Linear sketches are powerful algorithmic tools that turn an n-dimensional input into a concise lower-dimensional representation via a linear transformation. Such sketches have seen…
Low Rank Approximation and Regression in Input Sparsity Time
Kenneth L. Clarkson, David P. Woodruff
We design a new distribution over $\poly(r \eps^{-1}) \times n$ matrices so that for any fixed matrix of rank , with probability at least 9/10, $\norm{SAx}_…
The Fast Cauchy Transform and Faster Robust Linear Regression
Kenneth L. Clarkson, Petros Drineas, Malik Magdon-Ismail +3
We provide fast algorithms for overconstrained regression and related problems: for an input matrix and vector , in time we…
On Deterministic Sketching and Streaming for Sparse Recovery and Norm Estimation
Jelani Nelson, Huy Nguyen, David P. Woodruff
We study classic streaming and sparse recovery problems using deterministic linear sketches, including l1/l1 and linf/l1 sparse recovery problems (the latter also being known as l1…
Lower Bounds for Adaptive Sparse Recovery
Eric Price, David P. Woodruff
We give lower bounds for the problem of stable sparse recovery from /adaptive/ linear measurements. In this problem, one would like to estimate a vector from linea…