Theory Colloquium: Anupam Gupta
Speaker: Anupam Gupta
Date: Friday, November 18th, 2022
Time: 12:00 - 1:00 pm
Location: HH 1010
Host: Eric Vigoda
Title: Algorithms for Uncertain Environments: Going Beyond the Worst-Case
Analyzing the performance of algorithms in the worst-case and the average case have been two of the cornerstones of computer science: these give us techniques to understand how algorithms behave, in two different ways. Over the past two decades, there has been a concerted effort to understand the performance of algorithms in models that go beyond these two "extremes". In this talk I will discuss some of the proposed models and approaches, particularly for problems related to online algorithms, where decisions must be made sequentially without knowing future portions of the input.
Anupam is a professor in the Computer Science Department at Carnegie Mellon University. His research interests are broadly in the design and analysis of algorithms, primarily in optimization under uncertainty, in developing approximation algorithms for NP-hard optimization problems, and in understanding the algorithmic properties of metric spaces. He is an ACM Fellow, and a recipient of the Alfred P. Sloan Research Fellowship and the NSF Career award.