Algorithms and Uncertainty

Sahil Singla
03.09.2021 13:00 to 14:00

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 interconnections 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.