David Woodruff

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