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 Madhusudhan Pittu 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 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 Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness 2025 • Annual ACM Symposium on Theory of Computing • 395-406 Gribelyuk E, Lin H, Woodruff DP, Yu H, Zhou S Preprint Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness 2025 Gribelyuk E, Lin H, Woodruff DP, Yu H, Zhou S Journal Article Perfect Sampling in Turnstile Streams Beyond Small Moments 2025 • Proceedings of the ACM on Management of Data • 3(2):1-27 Woodruff DP, Xie S, Zhou S Conference Space Complexity of Minimum Cut Problems in Single-Pass Streams 2025 • Leibniz International Proceedings in Informatics • 325: Ding M, Garces A, Li J, Lin H, Nelson J, Shah V, 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 Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness 2025 • Annual ACM Symposium on Theory of Computing • 395-406 Gribelyuk E, Lin H, Woodruff DP, Yu H, Zhou S
Preprint Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness 2025 Gribelyuk E, Lin H, Woodruff DP, Yu H, Zhou S
Journal Article Perfect Sampling in Turnstile Streams Beyond Small Moments 2025 • Proceedings of the ACM on Management of Data • 3(2):1-27 Woodruff DP, Xie S, Zhou S
Conference Space Complexity of Minimum Cut Problems in Single-Pass Streams 2025 • Leibniz International Proceedings in Informatics • 325: Ding M, Garces A, Li J, Lin H, Nelson J, Shah V, Woodruff DP
