UCSB CS Theory Colloquium Series

Fall 2022

Friday, November 18, Noon Henley Hall 1010

Anupam Gupta (CMU)

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.