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 Conference Coresets for Multiple ℓ<inf>p</inf> Regression 2024 • Proceedings of Machine Learning Research • 235:53202-53233 Woodruff DP, Yasuda T Conference Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond 2024 • Proceedings of Machine Learning Research • 235:2086-2107 Axiotis K, Cohen-Addad V, Henzinger M, Jerome S, Mirrokni V, Saulpic D, Woodruff DP, Wunder M
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
Conference Coresets for Multiple ℓ<inf>p</inf> Regression 2024 • Proceedings of Machine Learning Research • 235:53202-53233 Woodruff DP, Yasuda T
Conference Data-Efficient Learning via Clustering-Based Sensitivity Sampling: Foundation Models and Beyond 2024 • Proceedings of Machine Learning Research • 235:2086-2107 Axiotis K, Cohen-Addad V, Henzinger M, Jerome S, Mirrokni V, Saulpic D, Woodruff DP, Wunder M
