Publications by David Woodruff

Conference

The product of Gaussian matrices is close to Gaussian

2021 • Leibniz International Proceedings in Informatics • 207:
Li Y, Woodruff DP

Journal Article

TIGHT BOUNDS FOR THE SUBSPACE SKETCH PROBLEM WITH APPLICATIONS

2021 • SIAM journal on computing (Print) • 50(4):1287-1335
Li Y, Wang R, Woodruff DP

Preprint

Truly Perfect Samplers for Data Streams and Sliding Windows

2021
Jayaram R, Woodruff DP, Zhou S

Preprint

A Framework for Adversarially Robust Streaming Algorithms

2020
Ben-Eliezer O, Jayaram R, Woodruff DP, Yogev E

Conference

A Framework for Adversarially Robust Streaming Algorithms

2020 63-80
Ben-Eliezer O, Jayaram R, Woodruff DP, Yogev E

Preprint

Approximation Algorithms for Sparse Principal Component Analysis

2020
Chowdhury A, Drineas P, Woodruff DP, Zhou S

Conference

Automatic Differentiation of Sketched Regression

2020 • Proceedings of Machine Learning Research • 108:4367-4376
Liao H, Pearlmutter BA, Potluru VK, Woodruff DP

Conference

Graph spanners in the message-passing model

2020 • Leibniz International Proceedings in Informatics • 151:
Manuel Fernández V, Woodruff DP, Yasuda T

Preprint

How to reduce dimension with PCA and random projections?

2020
Yang F, Liu S, Dobriban E, Woodruff DP

Preprint

Hutch++: Optimal Stochastic Trace Estimation

2020
Meyer RA, Musco C, Musco C, Woodruff DP

Conference

Input-Sparsity Low Rank Approximation in Schatten Norm

2020 • INTERNATIONAL CONFERENCE ON MACHINE LEARNING, VOL 119 • 119:
Li Y, Woodruff DP

Journal Article

Introduction to the Special Issue on SODA’18

2020 • ACM Transactions on Algorithms (TALG) • 16(1):1-2
Woodruff D

Preprint

Learning the Positions in CountSketch

2020
Liu S, Liu T, Vakilian A, Wan Y, Woodruff DP

Conference

LEARNING-AUGMENTED DATA STREAM ALGORITHMS

2020 • 8th International Conference on Learning Representations Iclr 2020
Jiang T, Li Y, Lin H, Ruan Y, Woodruff DP

Preprint

LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew

2020
Rashtchian C, Sharma A, Woodruff DP

Conference

LSF-Join: Locality Sensitive Filtering for Distributed All-Pairs Set Similarity Under Skew

2020 2998-3004
Rashtchian C, Sharma A, Woodruff D

Preprint

Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling

2020
Woodruff DP, Zandieh A

Conference

Near input sparsity time kernel embeddings via adaptive sampling

2020 • 37th International Conference on Machine Learning Icml 2020 • PartF168147-14:10255-10264
Woodruff DP, Zandieh A

Journal Article

Near Optimal Linear Algebra in the Online and Sliding Window Models

2020 • Annual Symposium on Foundations of Computer Science • 517-528
Braverman V, Drineas P, Musco C, Musco C, Upadhyay J, Woodruff DP, Zhou S

Preprint

Non-Adaptive Adaptive Sampling on Turnstile Streams

2020
Mahabadi S, Razenshteyn I, Woodruff DP, Zhou S

Conference

Non-adaptive Adaptive Sampling on Turnstile Streams

2020 • Annual ACM Symposium on Theory of Computing • 1251-1264
Mahabadi S, Razenshteyn I, Woodruff DP, Zhou S

Conference

Oblivious sketching of high-degree polynomial kernels

2020 • Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms • 2020-January:141-160
Ahle TD, Kapralov M, Knudsen JBT, Pagh R, Velingker A, Woodruff DP, Zandieh A

Preprint

Optimal $\ell_1$ Column Subset Selection and a Fast PTAS for Low Rank Approximation

2020
Mahankali AV, Woodruff DP

Conference

Optimal Communication-Distortion Tradeoff in Voting

2020 795-813
Mandal D, Shah N, Woodruff DP

Conference

Optimal Deterministic Coresets for Ridge Regression

2020 • INTERNATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND STATISTICS, VOL 108 • 108:4141-4149
Kacham P, Woodruff DP