Woodruff, David

91 publications

ICLR 2025 Beyond Worst-Case Dimensionality Reduction for Sparse Vectors Sandeep Silwal, David Woodruff, Qiuyi Zhang

ICLR 2025 LevAttention: Time, Space and Streaming Efficient Algorithm for Heavy Attentions Ravindran Kannan, Chiranjib Bhattacharyya, Praneeth Kacham, David Woodruff

ICML 2025 Maximum Coverage in Turnstile Streams with Applications to Fingerprinting Measures Alina Ene, Alessandro Epasto, Vahab Mirrokni, Hoai-An Nguyen, Huy Nguyen, David Woodruff, Peilin Zhong

NeurIPS 2025 Nearly-Linear Time and Massively Parallel Algorithms for $k$-Anonymity Kevin Aydin, Honghao Lin, David Woodruff, Peilin Zhong

ICML 2025 On Differential Privacy for Adaptively Solving Search Problems via Sketching Shiyuan Feng, Ying Feng, George Zhaoqi Li, Zhao Song, David Woodruff, Lichen Zhang

ICML 2025 On Fine-Grained Distinct Element Estimation Ilias Diakonikolas, Daniel Kane, Jasper C.H. Lee, Thanasis Pittas, David Woodruff, Samson Zhou

NeurIPS 2025 Query-Efficient Locally Private Hypothesis Selection via the Scheffe Graph Gautam Kamath, Alireza F. Pour, Matthew Regehr, David Woodruff

ICML 2025 Robust Sparsification via Sensitivity Chansophea Wathanak In, Yi Li, David Woodruff, Xuan Wu

ICLR 2025 Streaming Algorithms for $\ell_p$ Flows and $\ell_p$ Regression Amit Chakrabarti, Jeffrey Jiang, David Woodruff, Taisuke Yasuda

ICML 2025 Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra Raphael A Meyer, William Joseph Swartworth, David Woodruff

NeurIPSW 2024 A Theory for Compressibility of Graph Transformers for Transductive Learning Hamed Shirzad, Honghao Lin, Ameya Velingker, Balaji Venkatachalam, David Woodruff, Danica J. Sutherland

ICLR 2024 Adaptive Regret for Bandits Made Possible: Two Queries Suffice Zhou Lu, Qiuyi Zhang, Xinyi Chen, Fred Zhang, David Woodruff, Elad Hazan

NeurIPS 2024 Communication Bounds for the Distributed Experts Problem Zhihao Jia, Qi Pang, Trung Tran, David Woodruff, Zhihao Zhang, Wenting Zheng

ICML 2024 Coresets for Multiple $\ell_p$ Regression David Woodruff, Taisuke Yasuda

ICML 2024 Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David Woodruff, Michael Wunder

ICML 2024 Fast Sampling-Based Sketches for Tensors William Joseph Swartworth, David Woodruff

ICML 2024 Fast White-Box Adversarial Streaming Without a Random Oracle Ying Feng, Aayush Jain, David Woodruff

ICMLW 2024 GRASS: Compute Efficient Low-Memory LLM Training with Structured Sparse Gradients Aashiq Muhamed, Oscar Li, David Woodruff, Mona T. Diab, Virginia Smith

ICML 2024 High-Dimensional Geometric Streaming for Nearly Low Rank Data Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David Woodruff, Peilin Zhong

ICLR 2024 HyperAttention: Long-Context Attention in Near-Linear Time Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David Woodruff, Amir Zandieh

ICML 2024 Learning Multiple Secrets in Mastermind Milind Prabhu, David Woodruff

ICLR 2024 Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms Yi Li, Honghao Lin, David Woodruff

ICML 2024 Reweighted Solutions for Weighted Low Rank Approximation David Woodruff, Taisuke Yasuda

COLT 2023 $\ell_p$-Regression in the Arbitrary Partition Model of Communication Yi Li, Honghao Lin, David Woodruff

ICLR 2023 Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression Alexander Munteanu, Simon Omlor, David Woodruff

NeurIPS 2023 Computing Approximate $\ell_p$ Sensitivities Swati Padmanabhan, David Woodruff, Richard Zhang

ICML 2023 Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix Factorization Ameya Velingker, Maximilian Vötsch, David Woodruff, Samson Zhou

NeurIPS 2023 Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products Tamas Sarlos, Xingyou Song, David Woodruff, Richard Zhang

ICML 2023 Improved Algorithms for White-Box Adversarial Streams Ying Feng, David Woodruff

ICLR 2023 Learning the Positions in CountSketch Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David Woodruff

NeurIPSW 2023 Low-Width Approximations and Sparsification for Scaling Graph Transformers Hamed Shirzad, Balaji Venkatachalam, Ameya Velingker, Danica Sutherland, David Woodruff

NeurIPS 2023 Lower Bounds on Adaptive Sensing for Matrix Recovery Praneeth Kacham, David Woodruff

NeurIPS 2023 Near-Optimal $k$-Clustering in the Sliding Window Model David Woodruff, Peilin Zhong, Samson Zhou

NeurIPS 2023 On Robust Streaming for Learning with Experts: Algorithms and Lower Bounds David Woodruff, Fred Zhang, Samson Zhou

AISTATS 2023 Optimal Sketching Bounds for Sparse Linear Regression Tung Mai, Alexander Munteanu, Cameron Musco, Anup Rao, Chris Schwiegelshohn, David Woodruff

ICLR 2023 Robust Algorithms on Adaptive Inputs from Bounded Adversaries Yeshwanth Cherapanamjeri, Sandeep Silwal, David Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou

ICML 2023 Sharper Bounds for $\ell_p$ Sensitivity Sampling David Woodruff, Taisuke Yasuda

NeurIPS 2023 Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming Gregory Dexter, Petros Drineas, David Woodruff, Taisuke Yasuda

ICML 2022 Bounding the Width of Neural Networks via Coupled Initialization a Worst Case Analysis Alexander Munteanu, Simon Omlor, Zhao Song, David Woodruff

ICLR 2022 Fast Regression for Structured Inputs Raphael A Meyer, Cameron N Musco, Christopher P Musco, David Woodruff, Samson Zhou

ICML 2022 Learning Augmented Binary Search Trees Honghao Lin, Tian Luo, David Woodruff

ICLR 2022 Learning-Augmented $k$-Means Clustering Jon C. Ergun, Zhili Feng, Sandeep Silwal, David Woodruff, Samson Zhou

ICML 2022 Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time David Woodruff, Amir Zandieh

NeurIPS 2022 Optimal Query Complexities for Dynamic Trace Estimation David Woodruff, Fred Zhang, Richard Zhang

ICML 2022 Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra Nadiia Chepurko, Kenneth Clarkson, Lior Horesh, Honghao Lin, David Woodruff

ICML 2022 Sketching Algorithms and Lower Bounds for Ridge Regression Praneeth Kacham, David Woodruff

ICLR 2022 Triangle and Four Cycle Counting with Predictions in Graph Streams Justin Y Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David Woodruff, Michael Zhang

COLT 2021 Average-Case Communication Complexity of Statistical Problems Cyrus Rashtchian, David Woodruff, Peng Ye, Hanlin Zhu

ICML 2021 Dimensionality Reduction for the Sum-of-Distances Metric Zhili Feng, Praneeth Kacham, David Woodruff

COLT 2021 Exponentially Improved Dimensionality Reduction for L1: Subspace Embeddings and Independence Testing Yi Li, David Woodruff, Taisuke Yasuda

ICML 2021 Fast Sketching of Polynomial Kernels of Polynomial Degree Zhao Song, David Woodruff, Zheng Yu, Lichen Zhang

NeurIPS 2021 Few-Shot Data-Driven Algorithms for Low Rank Approximation Piotr Indyk, Tal Wagner, David Woodruff

ICML 2021 In-Database Regression in Input Sparsity Time Rajesh Jayaram, Alireza Samadian, David Woodruff, Peng Ye

ICLR 2021 Learning a Latent Simplex in Input Sparsity Time Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan, David Woodruff, Samson Zhou

NeurIPS 2021 Linear and Kernel Classification in the Streaming Model: Improved Bounds for Heavy Hitters Arvind Mahankali, David Woodruff

ICML 2021 Oblivious Sketching for Logistic Regression Alexander Munteanu, Simon Omlor, David Woodruff

NeurIPS 2021 Optimal Sketching for Trace Estimation Shuli Jiang, Hai Pham, David Woodruff, Richard Zhang

COLT 2021 Reduced-Rank Regression with Operator Norm Error Praneeth Kacham, David Woodruff

ICML 2021 Single Pass Entrywise-Transformed Low Rank Approximation Yifei Jiang, Yi Li, Yiming Sun, Jiaxin Wang, David Woodruff

ICML 2021 Streaming and Distributed Algorithms for Robust Column Subset Selection Shuli Jiang, Dennis Li, Irene Mengze Li, Arvind V Mahankali, David Woodruff

ICML 2020 Input-Sparsity Low Rank Approximation in Schatten Norm Yi Li, David Woodruff

ICML 2020 Near Input Sparsity Time Kernel Embeddings via Adaptive Sampling David Woodruff, Amir Zandieh

AISTATS 2020 Optimal Deterministic Coresets for Ridge Regression Praneeth Kacham, David Woodruff

NeurIPS 2020 Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes Minh Hoang, Nghia Hoang, Hai Pham, David Woodruff

NeurIPS 2020 WOR and $p$'s: Sketches for $\ell_p$-Sampling Without Replacement Edith Cohen, Rasmus Pagh, David Woodruff

NeurIPS 2019 Average Case Column Subset Selection for Entrywise $\ell_1$-Norm Loss Zhao Song, David Woodruff, Peilin Zhong

AISTATS 2019 Conditional Sparse $L_p$-Norm Regression with Optimal Probability John Hainline, Brendan Juba, Hai S. Le, David Woodruff

ICML 2019 Dimensionality Reduction for Tukey Regression Kenneth Clarkson, Ruosong Wang, David Woodruff

NeurIPS 2019 Efficient and Thrifty Voting by Any Means Necessary Debmalya Mandal, Ariel D Procaccia, Nisarg Shah, David Woodruff

ICML 2019 Faster Algorithms for Binary Matrix Factorization Ravi Kumar, Rina Panigrahy, Ali Rahimi, David Woodruff

NeurIPS 2019 Optimal Sketching for Kronecker Product Regression and Low Rank Approximation Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, David Woodruff

NeurIPS 2019 Regularized Weighted Low Rank Approximation Frank Ban, David Woodruff, Richard Zhang

NeurIPS 2019 Tight Dimensionality Reduction for Sketching Low Degree Polynomial Kernels Michela Meister, Tamas Sarlos, David Woodruff

ICML 2019 Tight Kernel Query Complexity of Kernel Ridge Regression and Kernel $k$-Means Clustering Taisuke Yasuda, David Woodruff, Manuel Fernandez

NeurIPS 2019 Total Least Squares Regression in Input Sparsity Time Huaian Diao, Zhao Song, David Woodruff, Xin Yang

NeurIPS 2019 Towards a Zero-One Law for Column Subset Selection Zhao Song, David Woodruff, Peilin Zhong

ICML 2018 Leveraging Well-Conditioned Bases: Streaming and Distributed Summaries in Minkowski $p$-Norms Charlie Dickens, Graham Cormode, David Woodruff

ICML 2018 Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order Vladimir Braverman, Stephen Chestnut, Robert Krauthgamer, Yi Li, David Woodruff, Lin Yang

NeurIPS 2018 On Coresets for Logistic Regression Alexander Munteanu, Chris Schwiegelshohn, Christian Sohler, David Woodruff

NeurIPS 2018 Robust Subspace Approximation in a Stream Roie Levin, Anish Prasad Sevekari, David Woodruff

NeurIPS 2018 Sublinear Time Low-Rank Approximation of Distance Matrices Ainesh Bakshi, David Woodruff

NeurIPS 2017 Approximation Algorithms for $\ell_0$-Low Rank Approximation Karl Bringmann, Pavel Kolev, David Woodruff

NeurIPS 2017 Is Input Sparsity Time Possible for Kernel Low-Rank Approximation? Cameron Musco, David Woodruff

NeurIPS 2017 Near Optimal Sketching of Low-Rank Tensor Regression Xingguo Li, Jarvis Haupt, David Woodruff

NeurIPS 2016 Communication-Optimal Distributed Clustering Jiecao Chen, He Sun, David Woodruff, Qin Zhang

ICML 2016 How to Fake Multiply by a Gaussian Matrix Michael Kapralov, Vamsi Potluru, David Woodruff

NeurIPS 2016 Sublinear Time Orthogonal Tensor Decomposition Zhao Song, David Woodruff, Huan Zhang

NeurIPS 2014 Improved Distributed Principal Component Analysis Yingyu Liang, Maria-Florina F Balcan, Vandana Kanchanapally, David Woodruff

NeurIPS 2014 Low Rank Approximation Lower Bounds in Row-Update Streams David Woodruff

NeurIPS 2014 Subspace Embeddings for the Polynomial Kernel Haim Avron, Huy Nguyen, David Woodruff

NeurIPS 2013 Sketching Structured Matrices for Faster Nonlinear Regression Haim Avron, Vikas Sindhwani, David Woodruff