Events

Theory Seminar: Machine Learning for Faster Optimization

Speaker: Ben Moseley, Carnegie Mellon University

Location: TBA

Date: Thursday, April 10, 2025

Location: Warren Weaver Hall, Room TBA

This talk explores the emerging area of algorithms with predictions, also known as learning-augmented algorithms. These methods incorporate machine-learned predictions into algorithmic design, allowing the algorithms to adapt to input distributions and achieve improved performance in runtime, space, or solution quality. The presentation will highlight recent advances in leveraging predictions to enhance the efficiency of optimization algorithms and dynamic graph algorithms. A key focus will be on achieving "instance-optimal" performance—where algorithms excel when predictions are accurate—while ensuring graceful degradation when predictions are imperfect. Through examples such as bipartite matching, the talk will demonstrate the transformative potential of this approach to significantly improve algorithmic efficiency.