David P. Woodruff

ORCID

Publication Activity (10 Years)

Years Active: 2002-2024
Publications (10 Years): 388

Top Venues

Massachusetts Institute of Technology, Cambridge, MA, USA (PHD)

Education History

Massachusetts Institute of Technology, Cambridge, MA, USA

PHD

Publications

Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang
A New Information Complexity Measure for Multi-pass Streaming with Applications. STOC (2024)
Kyriakos Axiotis, Vincent Cohen-Addad, Monika Henzinger, Sammy Jerome, Vahab Mirrokni, David Saulpic, David P. Woodruff, Michael Wunder
Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond. CoRR (2024)
Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong
Optimal Communication for Classic Functions in the Coordinator Model and Beyond. CoRR (2024)
Mark Braverman, Sumegha Garg, Qian Li, Shuo Wang, David P. Woodruff, Jiapeng Zhang
A New Information Complexity Measure for Multi-pass Streaming with Applications. CoRR (2024)
Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, Sushant Sachdeva, David P. Woodruff
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra. ITCS (2024)
Justin Y. Chen, Piotr Indyk, David P. Woodruff
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions. ITCS (2024)
David P. Woodruff
Approximation Algorithms on Matrices - With Some Database Applications! PODS Companion (2024)
Zhou Lu, Qiuyi Zhang, Xinyi Chen, Fred Zhang, David P. Woodruff, Elad Hazan
Adaptive Regret for Bandits Made Possible: Two Queries Suffice. ICLR (2024)
Praneeth Kacham, David P. Woodruff
Faster Algorithms for Schatten-p Low Rank Approximation. CoRR (2024)
Hossein Esfandiari, Praneeth Kacham, Vahab Mirrokni, David P. Woodruff, Peilin Zhong
Optimal Communication Bounds for Classic Functions in the Coordinator Model and Beyond. STOC (2024)
Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff, Jason Zhang
Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut. CoRR (2024)
Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David P. Woodruff, Guanghao Ye
Improving the Bit Complexity of Communication for Distributed Convex Optimization. STOC (2024)
Zhou Lu, Qiuyi Zhang, Xinyi Chen, Fred Zhang, David P. Woodruff, Elad Hazan
Adaptive Regret for Bandits Made Possible: Two Queries Suffice. CoRR (2024)
Rajesh Jayaram, David P. Woodruff, Samson Zhou
Streaming Algorithms with Few State Changes. Proc. ACM Manag. Data 2 (2) (2024)
David P. Woodruff, Taisuke Yasuda
Subspace Approximation. CoRR (2024)
Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, Amir Zandieh
HyperAttention: Long-context Attention in Near-Linear Time. ICLR (2024)
Yi Li, Honghao Lin, David P. Woodruff
Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms. ICLR (2024)
Hossein Esfandiari, Vahab Mirrokni, Praneeth Kacham, David P. Woodruff, Peilin Zhong
High-Dimensional Geometric Streaming for Nearly Low Rank Data. CoRR (2024)
Rajesh Jayaram, David P. Woodruff, Samson Zhou
Streaming Algorithms with Few State Changes. CoRR (2024)
William Swartworth, David P. Woodruff
Fast Sampling Based Sketches for Tensors. CoRR (2024)
David P. Woodruff, Taisuke Yasuda
Reweighted Solutions for Weighted Low Rank Approximation. CoRR (2024)
David P. Woodruff, Taisuke Yasuda
Regression. CoRR (2024)
Yu Cheng, Max Li, Honghao Lin, Zi-Yi Tai, David P. Woodruff, Jason Zhang
Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut. Proc. ACM Manag. Data 2 (2) (2024)
Ying Feng, Aayush Jain, David P. Woodruff
Fast White-Box Adversarial Streaming Without a Random Oracle. CoRR (2024)
Arvind V. Mahankali, David P. Woodruff, Ziyu Zhang
Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions. ITCS (2024)
Mehrdad Ghadiri, Yin Tat Lee, Swati Padmanabhan, William Swartworth, David P. Woodruff, Guanghao Ye
Improving the Bit Complexity of Communication for Distributed Convex Optimization. CoRR (2024)
Vincent Cohen-Addad, David P. Woodruff, Samson Zhou
Streaming Euclidean k-median and k-means with o(log n) Space. CoRR (2023)
Hai Pham, Young Jin Kim, Subhabrata Mukherjee, David P. Woodruff, Barnabás Póczos, Hany Hassan Awadalla
Task-Based MoE for Multitask Multilingual Machine Translation. CoRR (2023)
Alexander Munteanu, Simon Omlor, David P. Woodruff
and Logistic Regression. CoRR (2023)
Vincent Cohen-Addad, David P. Woodruff, Samson Zhou
Streaming Euclidean k-median and k-means with o(log n) Space. FOCS (2023)
Tung Mai, Alexander Munteanu, Cameron Musco, Anup B. Rao, Chris Schwiegelshohn, David P. Woodruff
Optimal Sketching Bounds for Sparse Linear Regression. CoRR (2023)
Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou
Robust Algorithms on Adaptive Inputs from Bounded Adversaries. CoRR (2023)
David P. Woodruff, Taisuke Yasuda
Sensitivity Sampling. CoRR (2023)
Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming. CoRR (2023)
Justin Y. Chen, Piotr Indyk, David P. Woodruff
Space-Optimal Profile Estimation in Data Streams with Applications to Symmetric Functions. CoRR (2023)
Ying Feng, David P. Woodruff
Improved Algorithms for White-Box Adversarial Streams. ICML (2023)
William Swartworth, David P. Woodruff
Optimal Eigenvalue Approximation via Sketching. CoRR (2023)
Tamás Sarlós, Xingyou Song, David P. Woodruff, Qiuyi Zhang
Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products. CoRR (2023)
Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou
On Differential Privacy and Adaptive Data Analysis with Bounded Space. CoRR (2023)
Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Fred Zhang, Qiuyi Zhang, Samson Zhou
Robust Algorithms on Adaptive Inputs from Bounded Adversaries. ICLR (2023)
David P. Woodruff, Fred Zhang, Samson Zhou
Streaming Algorithms for Learning with Experts: Deterministic Versus Robust. CoRR (2023)
Tung Mai, Alexander Munteanu, Cameron Musco, Anup Rao, Chris Schwiegelshohn, David P. Woodruff
Optimal Sketching Bounds for Sparse Linear Regression. AISTATS (2023)
David P. Woodruff, Peilin Zhong, Samson Zhou
Near-Optimal k-Clustering in the Sliding Window Model. NeurIPS (2023)
Alexander Munteanu, Simon Omlor, David P. Woodruff
Almost Linear Constant-Factor Sketching for $\ell_1$ and Logistic Regression. ICLR (2023)
Swati Padmanabhan, David P. Woodruff, Qiuyi (Richard) Zhang
Sensitivities. CoRR (2023)
Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou
Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization. CoRR (2023)
Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P. Woodruff, Amir Zandieh
HyperAttention: Long-context Attention in Near-Linear Time. CoRR (2023)
Ameya Velingker, Maximilian Vötsch, David P. Woodruff, Samson Zhou
Fast (1+ε)-Approximation Algorithms for Binary Matrix Factorization. ICML (2023)
Rajarshi Bhattacharjee, Gregory Dexter, Cameron Musco, Archan Ray, David P. Woodruff
Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra. CoRR (2023)
Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou
On Differential Privacy and Adaptive Data Analysis with Bounded Space. EUROCRYPT (3) (2023)
Praneeth Kacham, Rasmus Pagh, Mikkel Thorup, David P. Woodruff
Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming. FOCS (2023)
Ying Feng, David P. Woodruff
Improved Algorithms for White-Box Adversarial Streams. CoRR (2023)
David P. Woodruff, Taisuke Yasuda
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online. STOC (2023)
Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou
Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. SODA (2023)
Praneeth Kacham, David P. Woodruff
Lower Bounds on Adaptive Sensing for Matrix Recovery. CoRR (2023)
David P. Woodruff
Technical Perspective: Tapping the Link between Algorithmic Model Counting and Streaming. Commun. ACM 66 (9) (2023)
Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David P. Woodruff
Learning the Positions in CountSketch. CoRR (2023)
Yi Li, Honghao Lin, David P. Woodruff
-Regression in the Arbitrary Partition Model of Communication. CoRR (2023)
Gregory Dexter, Petros Drineas, David P. Woodruff, Taisuke Yasuda
Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming. CoRR (2023)
David P. Woodruff, Fred Zhang, Samson Zhou
On Robust Streaming for Learning with Experts: Algorithms and Lower Bounds. NeurIPS (2023)
Yi Li, Honghao Lin, David P. Woodruff
-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines. SODA (2023)
Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou
Polynomial Regression. SODA (2023)
David P. Woodruff, Peilin Zhong, Samson Zhou
Near-Optimal k-Clustering in the Sliding Window Model. CoRR (2023)
Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang
Recovery From Non-Decomposable Distance Oracles. IEEE Trans. Inf. Theory 69 (10) (2023)
Yi Li, Honghao Lin, David P. Woodruff
-Regression in the Arbitrary Partition Model of Communication. COLT (2023)
William Swartworth, David P. Woodruff
Optimal Eigenvalue Approximation via Sketching. STOC (2023)
Swati Padmanabhan, David P. Woodruff, Richard Zhang
Sensitivities. NeurIPS (2023)
Gregory Dexter, Petros Drineas, David P. Woodruff, Taisuke Yasuda
Sketching Algorithms for Sparse Dictionary Learning: PTAS and Turnstile Streaming. NeurIPS (2023)
Tamás Sarlós, Xingyou Song, David P. Woodruff, Richard Zhang
Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products. NeurIPS (2023)
David P. Woodruff, Taisuke Yasuda
Online Lewis Weight Sampling. SODA (2023)
Praneeth Kacham, David P. Woodruff
Lower Bounds on Adaptive Sensing for Matrix Recovery. NeurIPS (2023)
Rajesh Jayaram, David P. Woodruff
Towards Optimal Moment Estimation in Streaming and Distributed Models. ACM Trans. Algorithms 19 (3) (2023)
David P. Woodruff, Taisuke Yasuda
New Subset Selection Algorithms for Low Rank Approximation: Offline and Online. CoRR (2023)
Yi Li, Honghao Lin, Simin Liu, Ali Vakilian, David P. Woodruff
Learning the Positions in CountSketch. ICLR (2023)
Zhuangfei Hu, Xinda Li, David P. Woodruff, Hongyang Zhang, Shufan Zhang
Recovery from Non-Decomposable Distance Oracles. ITCS (2023)
Itai Dinur, Uri Stemmer, David P. Woodruff, Samson Zhou
On Differential Privacy and Adaptive Data Analysis with Bounded Space. IACR Cryptol. ePrint Arch. 2023 (2023)
David P. Woodruff, Taisuke Yasuda
Sensitivity Sampling. ICML (2023)
Alexander Munteanu, Simon Omlor, Zhao Song, David P. Woodruff
Bounding the Width of Neural Networks via Coupled Initialization A Worst Case Analysis. ICML (2022)
David P. Woodruff
Technical Perspective: Model Counting Meets Distinct Elements in a Data Stream. SIGMOD Rec. 51 (1) (2022)
Yi Li, Honghao Lin, David P. Woodruff
-Subspace Sketch Problem in Small Dimensions with Applications to Support Vector Machines. CoRR (2022)
Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou
Fast Regression for Structured Inputs. ICLR (2022)
Raphael A. Meyer, Cameron Musco, Christopher Musco, David P. Woodruff, Samson Zhou
Fast Regression for Structured Inputs. CoRR (2022)
Michael Kapralov, Amulya Musipatla, Jakab Tardos, David P. Woodruff, Samson Zhou
Noisy Boolean Hidden Matching with Applications. ITCS (2022)
Yi Li, David P. Woodruff
Tight Bounds for Sketching the Operator Norm, Schatten Norms, and Subspace Embeddings. CoRR (2022)
David P. Woodruff, Amir Zandieh
Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time. ICML (2022)
Alexander Munteanu, Simon Omlor, Zhao Song, David P. Woodruff
Bounding the Width of Neural Networks via Coupled Initialization - A Worst Case Analysis. CoRR (2022)
David P. Woodruff, Amir Zandieh
Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time. CoRR (2022)
Cameron Musco, Christopher Musco, David P. Woodruff, Taisuke Yasuda
Active Linear Regression for ℓp Norms and Beyond. FOCS (2022)
Vaidehi Srinivas, David P. Woodruff, Ziyu Xu, Samson Zhou
Memory Bounds for the Experts Problem. CoRR (2022)
Miklós Ajtai, Vladimir Braverman, T. S. Jayram, Sandeep Silwal, Alec Sun, David P. Woodruff, Samson Zhou
The White-Box Adversarial Data Stream Model. CoRR (2022)
Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang
Triangle and Four Cycle Counting with Predictions in Graph Streams. CoRR (2022)
David P. Woodruff, Taisuke Yasuda
High-Dimensional Geometric Streaming in Polynomial Space. FOCS (2022)
Justin Y. Chen, Talya Eden, Piotr Indyk, Honghao Lin, Shyam Narayanan, Ronitt Rubinfeld, Sandeep Silwal, Tal Wagner, David P. Woodruff, Michael Zhang
Triangle and Four Cycle Counting with Predictions in Graph Streams. ICLR (2022)
Yi Li, Honghao Lin, David P. Woodruff, Yuheng Zhang
Streaming Algorithms with Large Approximation Factors. APPROX/RANDOM (2022)
Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff, Samson Zhou
Optimal Algorithms for Linear Algebra in the Current Matrix Multiplication Time. CoRR (2022)
Ainesh Bakshi, Kenneth L. Clarkson, David P. Woodruff
Matrix-Vector Products. CoRR (2022)
Praneeth Kacham, David P. Woodruff
Sketching Algorithms and Lower Bounds for Ridge Regression. CoRR (2022)
Ruosong Wang, David P. Woodruff
Oblivious Subspace Embeddings. ACM Trans. Algorithms 18 (1) (2022)
Sepideh Mahabadi, David P. Woodruff, Samson Zhou
Adaptive Sketches for Robust Regression with Importance Sampling. CoRR (2022)
Jon C. Ergun, Zhili Feng, Sandeep Silwal, David P. Woodruff, Samson Zhou
Learning-Augmented $k$-means Clustering. ICLR (2022)

David P. Woodruff.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

David P. Woodruff