David Woodruff

Professor

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
Praneeth Kacham
Honghao Lin
Tai Yasuda

Research Statement

My current research interests are communication complexity, data stream algorithms and lower bounds, graph algorithms, machine learning, numerical linear algebra, sketching, and sparse recovery.

Recent Publications

David Woodruff ( 2022 ) Journal of the ACM, A Framework for Adversarially Robust Streaming Algorithms , Vol: 69 Issue: ( 2 )

Baweja A, Jia J, Woodruff DP ( 2022 ) Leibniz International Proceedings in Informatics, LIPIcs, An Efficient Semi-Streaming PTAS for Tournament Feedback Arc Set with Few Passes Vol: 215

Indyk P, Narayanan S, Woodruff DP ( 2022 ) Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Frequency Estimation with One-Sided Error Vol: 2022-January , Page(s): 695 - 707

Woodruff DP, Yasuda T ( 2022 ) Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Improved Algorithms for Low Rank Approximation from Sparsity Vol: 2022-January , Page(s): 2358 - 2403