Algorithms and Uncertainty

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.