David Woodruff Professor Website Office 7217 Gates and Hillman Centers Email dwoodruf@andrew.cmu.edu Department Computer Science Department Administrative Support Person Christina Contreras Research Interests Algorithms and Complexity Machine Learning Theory Advisees Honghao Lin Hoai-An Nguyen CSD Courses Taught 15451 - Spring, 2025 15651 - Spring, 2025 15851 - Spring, 2025 15851 - Spring, 2024 15651 - Spring, 2024 15451 - Spring, 2024 My current research interests are communication complexity, data stream algorithms and lower bounds, graph algorithms, machine learning, numerical linear algebra, sketching, and sparse recovery. Publications Conference BEYOND WORST-CASE DIMENSIONALITY REDUCTION FOR SPARSE VECTORS 2025 • 13th International Conference on Learning Representations Iclr 2025 • 31179-31212 Silwal S, Woodruff DP, Zhang Q Conference Guessing Efficiently for Constrained Subspace Approximation 2025 • Leibniz International Proceedings in Informatics • 334: Bhaskara A, Mahabadi S, Pittu MR, Vakilian A, Woodruff DP Journal Article Learning-augmented sketching offers improved performance for privacy preserving and secure GWAS 2025 • iScience • 28(3): Xu J, Zhu K, Cai J, Kockan C, Dokmai N, Cho H, Woodruff DP, Sahinalp SC Conference LEVATTENTION: TIME, SPACE AND STREAMING EFFICIENT ALGORITHM FOR HEAVY ATTENTIONS 2025 • 13th International Conference on Learning Representations Iclr 2025 • 15704-15720 Kannan R, Bhattacharya C, Kacham P, Woodruff DP Preprint Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness 2025 Gribelyuk E, Lin H, Woodruff DP, Yu H, Zhou S
Conference BEYOND WORST-CASE DIMENSIONALITY REDUCTION FOR SPARSE VECTORS 2025 • 13th International Conference on Learning Representations Iclr 2025 • 31179-31212 Silwal S, Woodruff DP, Zhang Q
Conference Guessing Efficiently for Constrained Subspace Approximation 2025 • Leibniz International Proceedings in Informatics • 334: Bhaskara A, Mahabadi S, Pittu MR, Vakilian A, Woodruff DP
Journal Article Learning-augmented sketching offers improved performance for privacy preserving and secure GWAS 2025 • iScience • 28(3): Xu J, Zhu K, Cai J, Kockan C, Dokmai N, Cho H, Woodruff DP, Sahinalp SC
Conference LEVATTENTION: TIME, SPACE AND STREAMING EFFICIENT ALGORITHM FOR HEAVY ATTENTIONS 2025 • 13th International Conference on Learning Representations Iclr 2025 • 15704-15720 Kannan R, Bhattacharya C, Kacham P, Woodruff DP
Preprint Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness 2025 Gribelyuk E, Lin H, Woodruff DP, Yu H, Zhou S
