אירועים והרצאות בפקולטה למדעי המחשב ע"ש הנרי ומרילין טאוב

Traditional computational models consider a one-shot computation, run on a single machine, with full knowledge of the input. In contrast, in many modern applications, the input is evolving, or is too large to be stored on any one machine, and is therefore partially unknown. These aspects of modern computation require decision-making under uncertainty. For example, in ride hailing applications, where drivers and riders arrive over time, the app needs to match users to each other quickly, despite uncertain information about future arrivals. In this talk I will present some of my work on algorithms for scenarios such as the above, where decisions must be made swiftly (and possibly irrevocably) following changes to their evolving input data. 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. Throughout, I will show how the use of randomization helps solve problems with uncertain input, highlighting key techniques underlying my work. I will then discuss the resolution of an open question concerning the use of randomization for the dynamic matching problem in the face of adaptively-changing data. Short 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 provable algorithms, particularly algorithms under uncertainty about the input, including online, dynamic, streaming and distributed algorithms.