TITLE: Algorithms and Uncertainty

ABSTRACT:

Modern algorithms have to regularly deal with uncertain inputs. This uncertainty can take many forms, e.g., in online advertisement future users are unknown (the input arrives online), in spectrum-auctions bidder valuations are unknown (the users are strategic), and in oil-drilling the amount of oil is unknown (the input is stochastic). Traditionally, there has not been significant overlap in the study of these different forms of uncertainty. I believe that studying these uncertainties together gives us a lot more power. In this talk, I will give an overview of my research in “Algorithms and Uncertainty” where I am able to successfully use these relationships.

Studying these different forms of uncertainty together allows us to find connections and build unifying techniques. As an example, I will talk about my progress on long-standing combinatorial auctions problems that deal with strategic inputs, by using techniques which were originally developed for online inputs. Moreover, a combined study of uncertainty helps us find richer cross-cutting models. For example, several important online problems do not admit good algorithms in the classical worst-case models. I will talk about how to give a “beyond the worst-case” analysis for such problems and obtain more nuanced performance guarantees, by using models/techniques arising in other forms of uncertainty.

BIO:

Sahil Singla is a research instructor (postdoc) jointly between Princeton University and Institute for Advanced Study. He received his Ph.D. in computer science from Carnegie Mellon University, where he was advised by Anupam Gupta and Manuel Blum. His research is in algorithms and uncertainty where the goal is to design optimal algorithms for uncertain inputs by studying different forms of uncertainty together. Singla has served on the program committees of the conferences SODA, ICALP, EC, and ESA. His research has been invited for talks at Highlights Beyond EC, at China Theory Week, at TCS+, and at Highlights of Algorithms. He recently contributed a chapter to the book Beyond the Worst-Case Analysis of Algorithms.

JOIN THE TALK HERE: https://bluejeans.com/946032411