Talk: Matching in Evolving Environments
David Wajc: Motwani Postdoctoral Fellow in Theoretical Computer Science at Stanford; PhD Computer Sciences, Carnegie Mellon
Also offered online
Abstract: A pervasive challenge in modern computing is one of uncertainty: how should we optimize over continuously-evolving user-generated data, promptly, despite uncertainty about future changes to the data? Instantiations of this question arise in domains as varied as ad serving, ride hailing and kidney exchanges. Fittingly, the search for a systematic approach to answering such questions has spurred a concerted effort to tackle long-standing open problems in the area of decision-making under uncertainty, and to develop generic algorithmic techniques for solving such problems.
In this talk I will present some of my work on algorithms for evolving data, where decisions must be made swiftly (and possibly irrevocably) following changes to their input. In particular, I will focus on online and dynamic problems involving matching pairs of people/items, mirroring the above motivating applications. First, I will discuss the resolution of two decades-old questions in the area of online algorithms, concerning the online matching and online edge-coloring problems. I will then discuss a general algorithmic framework for the design of dynamic matching algorithms that are robust to adaptively-changing data. Throughout, I will show how the use of randomization helps solve problems with uncertain input, and highlight key techniques used in my work, most prominently the use of the theory of Negative Association.
Bio: David Wajc is the 2020 Motwani Postdoctoral Fellow in theoretical computer science at Stanford University. He obtained his PhD at Carnegie Mellon University’s Computer Science Department, as part of the interdisciplinary program in Algorithms, Combinatorics, and Optimization. Before coming to CMU, he obtained his BSc and MSc in Computer Science at the Technion, receiving two excellence in teaching awards in the process. His research focuses on the design and analysis of algorithms, particularly ones dealing with uncertainty about the input, including online, dynamic, streaming and distributed algorithms.