CS Events

Computer Science Department Colloquium Optimization When You Don’t Know the Future
× Export Event Save iCal Send to Google Calendar Send to Yahoo Calendar Send to Outlook Live Send to Microsoft Outlook Save iCal Preserve formatting in description (only supported in some calendar applications) Close Thursday, April 06, 2023, 10:30am - 11:30am

Speaker: Roie Levin

Bio

Roie is a Fulbright Postdoctoral Fellow at Tel Aviv University, working with Niv Buchbinder. He received his PhD in Algorithms, Combinatorics and Optimization (ACO) from Carnegie Mellon University where he was advised by Anupam Gupta. Before that, he was a research engineer at the Allen Institute for AI in Seattle, and before that he received bachelor degrees in math and computer science from Brown University. Roie's research spans approximation algorithms, algorithms for uncertain environments, and submodular optimization (the discrete cousin of convex optimization).

Location : Core 301

: 

Event Type: Computer Science Department Colloquium

Abstract: Discrete optimization is a powerful toolbox used ubiquitously in computer science and beyond; yet, for many applications, it is unrealistic to expect a complete and accurate description of the problem at hand. How should we approach solving problems when we are uncertain about the input? In this talk I will survey my research on algorithms under uncertainty, which is a framework for answering such questions. I will talk about algorithmic models that try to capture different kinds of uncertainty in optimization problems, the interplay between computational hardness and information, and applications to a variety of common algorithmic tasks.My work has focused on three different kinds of uncertain environments: (a) Online settings where the input is revealed piecemeal, and the algorithm must commit to irrevocable decisions as it maintains feasibility. (b) Dynamic settings where the input changes over time, and the goal is to maintain a feasible solution that moves as little as possible between updates. (c) Streaming settings where the input is too large to hold in memory all at once, and the algorithm must compute a solution with only limited memory after few sequential passes over the data. An important motif throughout my research is the study of submodular functions, which are a natural discrete analog of convex/concave functions

: 

Contact  Karthik Srikanta and Peng Zhang