2.2k citations
- IBM (United States)US73 papers
- Stanford UniversityUS62 papers
- IBM Research - Thomas J. Watson Research CenterUS42 papers
- University of California, BerkeleyUS22 papers
- IBM Research - ZurichCH21 papers
- California Institute of TechnologyUS20 papers
- École Polytechnique Fédérale de LausanneCH15 papers
- Massachusetts Institute of TechnologyUS14 papers
- Max Planck Institute of Microstructure PhysicsDE13 papers
- ETH ZurichCH10 papers
- Princeton UniversityUS10 papers
- SLAC National Accelerator LaboratoryUS10 papers
4 papers · 2 filters
Sketching as a Tool for Numerical Linear Algebra
David P. Woodruff
This survey highlights the recent advances in algorithms for numerical linear algebra that have come from the technique of linear sketching, whereby given a matrix, one first compr…
Subsampled Power Iteration: a Unified Algorithm for Block Models and Planted CSP's
Vitaly Feldman, Will Perkins, Santosh Vempala
We present an algorithm for recovering planted solutions in two well-known models, the stochastic block model and planted constraint satisfaction problems, via a common generalizat…
Optimal CUR Matrix Decompositions
Christos Boutsidis, David P. Woodruff
The CUR decomposition of an matrix finds an matrix with a subset of columns of together with an matrix with a subset…
The Sketching Complexity of Graph Cuts
Alexandr Andoni, Robert Krauthgamer, David P. Woodruff
We study the problem of sketching an input graph, so that given the sketch, one can estimate the weight of any cut in the graph within factor . We present lower and upper boun…