← Authors

David Woodruff

90 papers · 2013–2025 · 6 conferences · across top CS/AI conferences

Achievements

🌍 Conference Polyglot (6) 🐣 Hot Topic Early Bird πŸ—ΊοΈ Taxonomy Completionist (16) 🧭 Keyword Pioneer πŸŒ‰ Interdisciplinary Bridge πŸƒ Academic Marathon (12) 🐝 Cross-Pollinator (13) 🌈 Renaissance Researcher (6) 🏠 Conference Loyalist (32) 🧬 Topic Evolution πŸ† Keyword Champion (2) πŸ”¬ Deep Specialist (27) πŸ‘‘ Triple Crown πŸ—ƒοΈ Keyword Collector (74) ⚑ Prolific Year (13) πŸ“ˆ Trend Setter ❓ The Questioner πŸ’Ž Century Club (90) πŸ”₯ Unstoppable (10)

Conferences

ICML (34) NIPS (32) ICLR (13) COLT (6) AISTATS (4) EMNLP (1)

Top co-authors

Zhao Song (9) Samson Zhou (8) Yi Li (8) Taisuke Yasuda (7) Praneeth Kacham (7) Honghao Lin (6) Richard Zhang (5) Alexander Munteanu (5) Peilin Zhong (5) Vahab Mirrokni (4)

Keywords

low rank approximation (13) dimensionality reduction (11) low-rank approximation (10) streaming algorithm (9) subspace embedding (9) matrix approximation (9) matrix factorization (8) numerical linear algebra (7) approximation algorithm (6) communication complexity (6) lower bound (5) random projection (5) randomized algorithm (5) kernel methods (5) sublinear algorithm (5) matrix sketching (5) polynomial kernel (4) matrix multiplication (4) oblivious sketching (4) leverage score (3)

Papers

Robust Sparsification via Sensitivity ICML 2025
Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures ICML 2025
On Fine-Grained Distinct Element Estimation ICML 2025
Streaming Algorithms For $\ell_p$ Flows and $\ell_p$ Regression ICLR 2025
LevAttention: Time, Space and Streaming Efficient Algorithm for Heavy Attentions ICLR 2025
On Differential Privacy for Adaptively Solving Search Problems via Sketching ICML 2025
Beyond Worst-Case Dimensionality Reduction for Sparse Vectors ICLR 2025
Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra ICML 2025
Fast Sampling-Based Sketches for Tensors ICML 2024
Learning Multiple Secrets in Mastermind ICML 2024
Fast White-Box Adversarial Streaming Without a Random Oracle ICML 2024
High-Dimensional Geometric Streaming for Nearly Low Rank Data ICML 2024
Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond ICML 2024
Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms ICLR 2024
GRASS: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradients EMNLP 2024
Communication Bounds for the Distributed Experts Problem NIPS 2024
HyperAttention: Long-context Attention in Near-Linear Time ICLR 2024
Adaptive Regret for Bandits Made Possible: Two Queries Suffice ICLR 2024
Reweighted Solutions for Weighted Low Rank Approximation ICML 2024
Coresets for Multiple $\ell_p$ Regression ICML 2024
Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression ICLR 2023
Sharper Bounds for $\ell_p$ Sensitivity Sampling ICML 2023
Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization ICML 2023
Improved Algorithms for White-Box Adversarial Streams ICML 2023
Near-Optimal $k$-Clustering in the Sliding Window Model NIPS 2023
Computing Approximate $\ell_p$ Sensitivities NIPS 2023
Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming NIPS 2023
Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products NIPS 2023
Lower Bounds on Adaptive Sensing for Matrix Recovery NIPS 2023
On Robust Streaming for Learning with Experts: Algorithms and Lower Bounds NIPS 2023
Optimal Sketching Bounds for Sparse Linear Regression AISTATS 2023
$\ell_p$-Regression in the Arbitrary Partition Model of Communication COLT 2023
Robust Algorithms on Adaptive Inputs from Bounded Adversaries ICLR 2023
Learning the Positions in CountSketch ICLR 2023
Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra ICML 2022
Bounding the Width of Neural Networks via Coupled Initialization A Worst Case Analysis ICML 2022
Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time ICML 2022
Fast Regression for Structured Inputs ICLR 2022
Triangle and Four Cycle Counting with Predictions in Graph Streams ICLR 2022
Optimal Query Complexities for Dynamic Trace Estimation NIPS 2022
Learning-Augmented $k$-means Clustering ICLR 2022
Learning Augmented Binary Search Trees ICML 2022
Sketching Algorithms and Lower Bounds for Ridge Regression ICML 2022
Learning a Latent Simplex in Input Sparsity Time ICLR 2021
In-Database Regression in Input Sparsity Time ICML 2021
Few-Shot Data-Driven Algorithms for Low Rank Approximation NIPS 2021
Fast Sketching of Polynomial Kernels of Polynomial Degree ICML 2021
Optimal Sketching for Trace Estimation NIPS 2021
Dimensionality Reduction for the Sum-of-Distances Metric ICML 2021
Oblivious Sketching for Logistic Regression ICML 2021
Single Pass Entrywise-Transformed Low Rank Approximation ICML 2021
Reduced-Rank Regression with Operator Norm Error COLT 2021
Exponentially Improved Dimensionality Reduction for l1: Subspace Embeddings and Independence Testing COLT 2021
Average-Case Communication Complexity of Statistical Problems COLT 2021
Streaming and Distributed Algorithms for Robust Column Subset Selection ICML 2021
Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters NIPS 2021
Optimal Deterministic Coresets for Ridge Regression AISTATS 2020
Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes NIPS 2020
WOR and $p$'s: Sketches for $\ell_p$-Sampling Without Replacement NIPS 2020
Input-Sparsity Low Rank Approximation in Schatten Norm ICML 2020
Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling ICML 2020
Faster Algorithms for Binary Matrix Factorization ICML 2019
Conditional Sparse $L_p$-norm Regression With Optimal Probability AISTATS 2019
Towards a Zero-One Law for Column Subset Selection NIPS 2019
Efficient and Thrifty Voting by Any Means Necessary NIPS 2019
Tight Dimensionality Reduction for Sketching Low Degree Polynomial Kernels NIPS 2019
Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss NIPS 2019
Regularized Weighted Low Rank Approximation NIPS 2019
Total Least Squares Regression in Input Sparsity Time NIPS 2019
Optimal Sketching for Kronecker Product Regression and Low Rank Approximation NIPS 2019
Dimensionality Reduction for Tukey Regression ICML 2019
Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$-means Clustering ICML 2019
On Coresets for Logistic Regression NIPS 2018
Robust Subspace Approximation in a Stream NIPS 2018
Leveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski $p$-Norms ICML 2018
Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order ICML 2018
Sublinear Time Low-Rank Approximation of Distance Matrices NIPS 2018
Sketching for Kronecker Product Regression and P-splines AISTATS 2018
Approximation Algorithms for $\ell_0$-Low Rank Approximation NIPS 2017
Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? NIPS 2017
Near Optimal Sketching of Low-Rank Tensor Regression NIPS 2017
Sublinear Time Orthogonal Tensor Decomposition NIPS 2016
How to Fake Multiply by a Gaussian Matrix ICML 2016
Communication-Optimal Distributed Clustering NIPS 2016
Improved Distributed Principal Component Analysis NIPS 2014
Low Rank Approximation Lower Bounds in Row-Update Streams NIPS 2014
Subspace Embeddings for the Polynomial Kernel NIPS 2014
Principal Component Analysis and Higher Correlations for Distributed Data COLT 2014
Subspace Embeddings and \ell_p-Regression Using Exponential Random Variables COLT 2013
Sketching Structured Matrices for Faster Nonlinear Regression NIPS 2013