170 citations · 876 across the 146 of their papers we have counts for
142 papers · 1 filter
-Regression in the Arbitrary Partition Model of Communication
Yi Li, Honghao Lin, David P. Woodruff
We consider the randomized communication complexity of the distributed -regression problem in the coordinator model, for . In this problem, there is a coordinat…
Improved Algorithms for White-Box Adversarial Streams
Ying Feng, David P. Woodruff
We study streaming algorithms in the white-box adversarial stream model, where the internal state of the streaming algorithm is revealed to an adversary who adaptively generates th…
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}…
Sharper Bounds for Sensitivity Sampling
David P. Woodruff, Taisuke Yasuda
In large scale machine learning, random sampling is a popular way to approximate datasets by a small representative subset of examples. In particular, sensitivity sampling is an in…
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra
Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco +3
Let satisfy , where is the all ones matrix and is the spectral norm. It is well-kno…
Optimal Eigenvalue Approximation via Sketching
William Swartworth, David P. Woodruff
Given a symmetric matrix , we show from the simple sketch , where is a Gaussian matrix with rows, that there is a procedure for approximating all eigen…