Refreshments are available starting at 10:30 a.m. The lecture will begin at 10:45 a.m.
Abstract
The area of algorithms with predictions, or learning-augmented algorithms, considers the setting where an algorithm is given advice in the form of predictions, such as from a machine learning model. For example, when scheduling jobs, one could obtain a prediction of each job’s service time. Queueing systems present many opportunities for applying learning-augmented algorithms, raising numerous open questions about how predictions can be effectively leveraged to improve scheduling decisions. Several recent studies have started the exploration of queues with predicted service times instead of exact ones, typically aiming to minimize the average time a job spends in the system. We review this recent work, highlighting the potential effectiveness of predictions and providing a collection of open questions regarding the performance of queueing systems using predictions. We also provide some comments on applications of predictions for scheduling for large language model systems.
Speaker Biography
Michael Mitzenmacher’s research interests include the design and analysis of algorithms, particularly for networks, databases, and other systems. He has authored or coauthored over 250 conference and journal publications on a variety of topics, including coding theory, queueing theory, compression, sketch data structures, and algorithms with predictions. He is the coauthor of Probability and Computing, a textbook on randomized algorithms and probabilistic techniques in computer science. He is a Fellow of the ACM and the Institute of Electrical and Electronics Engineers, and received the ACM Paris Kanellakis Theory and Practice Award for his paper, “The Power of Two Choices in Randomized Load Balancing.”
Zoom link >>
This lecture is sponsored by the Nathan Krasnopoler Memorial Fund, established at the Whiting School of Engineering to benefit the Johns Hopkins chapter of the Association for Computing Machinery.