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

Abstract: 

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.

Bio:

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.