[Theory Lunch 03/05] Sahil Singla: Algorithms and Uncertainty
13 views
Skip to first unread message
Haoming Li
Feb 27, 2021, 6:35:51 PM2/27/21
to usc-theo...@googlegroups.com, usc-t...@googlegroups.com
USC CS Theory Lunch:
Algorithms and Uncertainty
Speaker: Sahil Singla (https://www.cs.princeton.edu/~singla/)
Time: 03/05/21 11:45am PST
Location: https://usc.zoom.us/j/94386654763
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.
Algorithms and Uncertainty
Speaker: Sahil Singla (https://www.cs.princeton.edu/~singla/)
Time: 03/05/21 11:45am PST
Location: https://usc.zoom.us/j/94386654763
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) at Princeton University and the Institute for Advanced Study. Before coming to Princeton, he finished his PhD in Computer Science at Carnegie Mellon University where he was advised by Manuel Blum and Anupam Gupta. Earlier, He received a master's degree from University of Waterloo and a bachelor's degree from Indian Institute of Technology, Delhi, in Computer Science.
Reply all
Reply to author
Forward
0 new messages