Please note: This lecture will take place in DC 1302 and online.
Sanjeev Khanna
Henry Salvatori Professor of Computer and Information Science
University of Pennsylvania
The maximum matching problem occupies a central place in combinatorial optimization, and its study is intimately connected to major algorithmic advances. While much of the long and rich history of the matching problem revolves around classical algorithms, characterized by linear-time and linear-space as gold standards of efficiency, the past few decades have witnessed the emergence of an exciting new area of sublinear algorithms. The field of sublinear computation is driven by the challenges of computing over very large datasets, and focuses on the design of algorithms that use computational resources significantly smaller than the input size. Remarkably, much like in the classical setting, the matching problem has come to play a pivotal role in the study of sublinear algorithms.
This talk will be a (personally biased) journey through some surprising algorithmic results and unexpected connections discovered by exploring the matching problem through the lens of sublinear algorithms.
Bio: Sanjeev Khanna is a Henry Salvatori Professor of Computer and Information Science at University of Pennsylvania. He received his Ph.D. in Computer Science from Stanford University in 1996, and subsequently spent three years as a researcher at Bell Labs before joining the University of Pennsylvania.
Sanjeev’s primary research interests are in approximation algorithms and hardness of approximation, combinatorial optimization, and sublinear algorithms. He is an ACM Fellow, a Guggenheim Fellow, and a Sloan Fellow. Sanjeev is also a recipient of the S. Reid Warren, Jr. and Lindback awards for distinguished teaching at the University of Pennsylvania.