Publications by David Woodruff

Journal Article

Optimal CUR Matrix Decompositions

2017 • SIAM journal on computing (Print) • 46(2):543-589
Boutsidis C, Woodruff DP

Preprint

Optimal lower bounds for universal relation, and for samplers and finding duplicates in streams

2017
Kapralov M, Nelson J, Pachocki J, Wang Z, Woodruff DP, Yahyazadeh M

Conference

Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams

2017 • Annual Symposium on Foundations of Computer Science • 475-486
Kapralov M, Nelson J, Pachocki J, Wang Z, Woodruff DP, Yahyazadeh M

Preprint

Robust Communication-Optimal Distributed Clustering Algorithms

2017
Awasthi P, Bakshi A, Balcan M-F, White C, Woodruff D

Conference

Sharper bounds for regularized data fitting

2017 • Leibniz International Proceedings in Informatics • 81:
Avron H, Clarkson KL, Woodruff DP

Conference

Sketching for geometric problems

2017 • Leibniz International Proceedings in Informatics • 87:
Woodruff DP

Preprint

Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness

2017
Musco C, Netrapalli P, Sidford A, Ubaru S, Woodruff DP

Preprint

Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices

2017
Musco C, Woodruff DP

Conference

Sublinear Time Low-Rank Approximation of Positive Semidefinite Matrices

2017 • Annual Symposium on Foundations of Computer Science • 672-683
Musco C, Woodruff DP

Journal Article

When distributed computation is communication expensive

2017 • Distributed Computing • 30(5):309-323
Woodruff DP, Zhang Q

Conference

An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems

2016 • Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems • 385-400
Bhattacharyya A, Dey P, Woodruff DP

Conference

Beating CountSketch for heavy hitters in insertion streams

2016 • Annual ACM Symposium on Theory of Computing • 740-753
Braverman V, Chestnut SR, Ivkin N, Woodruff DP

Preprint

BPTree: an $\ell_2$ heavy hitters algorithm using constant memory

2016
Braverman V, Chestnut SR, Ivkin N, Nelson J, Wang Z, Woodruff DP

Conference

Brief Announcement

2016 397-399
Esfandiari H, Hajiaghayi M, Woodruff DP

Journal Article

Certifying Equality With Limited Interaction

2016 • Algorithmica • 76(3):796-845
Brody J, Chakrabarti A, Kondapally R, Woodruff DP, Yaroslavtsev G

Journal Article

Communication Efficient Distributed Kernel Principal Component Analysis

2016 • Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining • 725-734
Balcan M-F, Liang Y, Song L, Woodruff D, Xie B

Conference

Communication lower bounds for statistical estimation problems via a distributed data processing inequality

2016 • Annual ACM Symposium on Theory of Computing • 1011-1020
Braverman M, Garg A, Ma T, Nguyen HL, Woodruff DP

Conference

Communication-optimal distributed clustering

2016 • Advances in Neural Information Processing Systems • 3727-3735
Chen J, Sun H, Woodruff DP, Zhang Q

Conference

Distributed Low Rank Approximation of Implicit Functions of a Matrix

2016 847-858
Woodruff DP, Zhong P

Journal Article

Editorial to the Special Issue on SODA'12

2016 • ACM Transactions on Algorithms (TALG) • 12(1):1-1
Woodruff D

Preprint

Faster Kernel Ridge Regression Using Sketching and Preconditioning

2016
Avron H, Clarkson KL, Woodruff DP

Chapter

Frequency Moments

2016 1-2
Woodruff D

Journal Article

Frequent Directions: Simple and Deterministic Matrix Sketching

2016 • SIAM journal on computing (Print) • 45(5):1762-1792
Ghashami M, Liberty E, Phillips JM, Woodruff DP

Journal Article

Guest Editorial for Information Complexity and Applications

2016 • Algorithmica • 76(3):595-596
Braverman M, Woodruff DP

Conference

How to fake multiply by a Gaussian matrix

2016 • 33rd International Conference on Machine Learning, ICML 2016 • 5:3053-3085
Kapralov M, Potluru VK, Woodruff DP