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 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 Approximation Algorithms on Matrices - With Some Database Applications! 2024 • Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems • 5-6 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 Approximation Algorithms on Matrices - With Some Database Applications! 2024 • Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems • 5-6 Woodruff DP
