David Woodruff

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