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 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 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 Preprint Fast Sampling Based Sketches for Tensors 2024 Swartworth W, Woodruff DP Preprint High-Dimensional Geometric Streaming for Nearly Low Rank Data 2024 Esfandiari H, Mirrokni V, Kacham P, Woodruff DP, Zhong P
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
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
Preprint High-Dimensional Geometric Streaming for Nearly Low Rank Data 2024 Esfandiari H, Mirrokni V, Kacham P, Woodruff DP, Zhong P
