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 15651 - Spring, 2024 15451 - Spring, 2024 15851 - 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 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 Preprint A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches 2024 Gribelyuk E, Lin H, Woodruff DP, Yu H, Zhou S Conference A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches 2024 • Annual Symposium on Foundations of Computer Science • 00:2318-2343 Gribelyuk E, Lin H, Woodruff DP, Yu H, Zhou S Conference ADAPTIVE REGRET FOR BANDITS MADE POSSIBLE: TWO QUERIES SUFFICE 2024 • 12th International Conference on Learning Representations, ICLR 2024 Lu Z, Zhang Q, Chen X, Zhang F, Woodruff DP, Hazan E
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
Preprint A Strong Separation for Adversarially Robust $\ell_0$ Estimation for Linear Sketches 2024 Gribelyuk E, Lin H, Woodruff DP, Yu H, Zhou S
Conference A Strong Separation for Adversarially Robust ℓ0 Estimation for Linear Sketches 2024 • Annual Symposium on Foundations of Computer Science • 00:2318-2343 Gribelyuk E, Lin H, Woodruff DP, Yu H, Zhou S
Conference ADAPTIVE REGRET FOR BANDITS MADE POSSIBLE: TWO QUERIES SUFFICE 2024 • 12th International Conference on Learning Representations, ICLR 2024 Lu Z, Zhang Q, Chen X, Zhang F, Woodruff DP, Hazan E
