log in  |  register  |  feedback?  |  help  |  web accessibility
Logo
Algorithms and Uncertainty
Sahil Singla
https://umd.zoom.us/j/94543765116?pwd=clY3MVV5Z1g4T2xpdnJMdjFiMFhYdz09
Tuesday, March 9, 2021, 1:00-2:00 pm Calendar
  • You are subscribed to this talk through .
  • You are watching this talk through .
  • You are subscribed to this talk. (unsubscribe, watch)
  • You are watching this talk. (unwatch, subscribe)
  • You are not subscribed to this talk. (watch, subscribe)
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 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.

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. Sahil 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ā€¯.

This talk is organized by Richa Mathur