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 Preprint Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness 2025 Gribelyuk E, Lin H, Woodruff DP, Yu H, 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 Conference Tight Sampling Bounds for Eigenvalue Approximation 2025 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 1:489-516 Swartworth W, Woodruff DP Conference A New Information Complexity Measure for Multi-pass Streaming with Applications 2024 • Annual ACM Symposium on Theory of Computing • 1781-1792 Braverman M, Garg S, Li Q, Wang S, Woodruff DP, Zhang J
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
Preprint Lifting Linear Sketches: Optimal Bounds and Adversarial Robustness 2025 Gribelyuk E, Lin H, Woodruff DP, Yu H, 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
Conference Tight Sampling Bounds for Eigenvalue Approximation 2025 • Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms • 1:489-516 Swartworth W, Woodruff DP
Conference A New Information Complexity Measure for Multi-pass Streaming with Applications 2024 • Annual ACM Symposium on Theory of Computing • 1781-1792 Braverman M, Garg S, Li Q, Wang S, Woodruff DP, Zhang J
