ORIE Special Seminar: David Wajc (Stanford)




Matching in Evolving Environments

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.

David Wajc is the 2020 Motwani Postdoctoral Fellow in theoretical computer science at Stanford University. He obtained his Ph.D. 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 B.Sc. and M.Sc. 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.