Nearly-optimal bounds for sparse recovery in generic norms, with applications to k-median sketching
- Arturs Backurs
- Piotr Indyk
- et al.
- 2016
- SODA 2016
Publications
Date
Featured collections
Popular topics
94 results for David P. Woodruff
Input Sparsity and Hardness for Robust Subspace Approximation
- Kenneth L. Clarkson
- David P. Woodruff
- 2015
- FOCS 2015
The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication
- Dirk Van Gucht
- Ryan Williams
- et al.
- 2015
- SIGMOD/PODS 2015
Improved testing of low rank matrices
- Yi Li
- Zhengyu Wang
- et al.
- 2014
- KDD 2014
Beyond set disjointness: The communication complexity of finding the intersection
- Joshua Brody
- Amit Chakrabarti
- et al.
- 2014
- PODC 2014
Is min-wise hashing optimal for summarizing set intersection?
- Rasmus Pagh
- Morten Stöckel
- et al.
- 2014
- SIGMOD/PODS 2014
Optimal CUR matrix decompositions
- Christos Boutsidis
- David P. Woodruff
- 2014
- STOC 2014
Turnstile streaming algorithms might as well be linear sketches
- Yi Li
- Huy L. Nguyễn
- et al.
- 2014
- STOC 2014
An optimal lower bound for distinct elements in the message passing model
- David P. Woodruff
- Qin Zhang
- 2014
- SODA 2014
On sketching matrix norms and the top singular vector
- Yi Li
- Huy L. Nguyễn
- et al.
- 2014
- SODA 2014