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 Praneeth Kacham Honghao Lin Hoai-An Nguyen Madhusudhan Pittu CSD Courses Taught 15851 - Spring, 2024 15651 - Spring, 2024 15451 - Spring, 2024 Research/Teaching 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. Publications Conference Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions 2024 • Leibniz International Proceedings in Informatics • 287: Mahankali AV, Woodruff DP, Zhang Z Conference Space-optimal profile estimation in data streams with applications to symmetric functions 2024 • Leibniz International Proceedings in Informatics • 287: Chen JY, Indyk P, Woodruff DP Conference Universal matrix sparsifiers and fast deterministic algorithms for linear Algebra 2024 • Leibniz International Proceedings in Informatics • 287: Bhattacharjee R, Dexter G, Musco C, Ray A, Sushant Sachdeva, Woodruff DP Conference Fast (1 + ε)-Approximation Algorithms for Binary Matrix Factorization 2023 • Proceedings of Machine Learning Research • 202:34952-34977 Velingker A, Vötsch M, Woodruff DP, Zhou S Conference Improved Algorithms for White-Box Adversarial Streams 2023 • Proceedings of Machine Learning Research • 202:9962-9975 Feng Y, Woodruff DP
Conference Near-Linear Time and Fixed-Parameter Tractable Algorithms for Tensor Decompositions 2024 • Leibniz International Proceedings in Informatics • 287: Mahankali AV, Woodruff DP, Zhang Z
Conference Space-optimal profile estimation in data streams with applications to symmetric functions 2024 • Leibniz International Proceedings in Informatics • 287: Chen JY, Indyk P, Woodruff DP
Conference Universal matrix sparsifiers and fast deterministic algorithms for linear Algebra 2024 • Leibniz International Proceedings in Informatics • 287: Bhattacharjee R, Dexter G, Musco C, Ray A, Sushant Sachdeva, Woodruff DP
Conference Fast (1 + ε)-Approximation Algorithms for Binary Matrix Factorization 2023 • Proceedings of Machine Learning Research • 202:34952-34977 Velingker A, Vötsch M, Woodruff DP, Zhou S
Conference Improved Algorithms for White-Box Adversarial Streams 2023 • Proceedings of Machine Learning Research • 202:9962-9975 Feng Y, Woodruff DP
