Invited Talk by Sagar Kale on Streaming Algorithms

Invited Talk by Sagar Kale on Streaming Algorithms

Title of the Talk: Streaming Algorithms for Matching Problems
Speaker: Sagar Kale
Date &Time: 18th October 2019
Venue: Room No-A-119

Abstract:

The advent of big data necessitated design of algorithms that could cope with it. Streaming algorithms are viable for big data because they process their input sequentially and use a small amount of working memory. In this talk, I will present my research on streaming algorithms for matching problems. Matching problems have played a significant historical role in not just combinatorial optimization specifically but computer science at large and are our benchmark problems for development and understanding of a computational model. Indeed, studying them in the streaming model has led me to fastest algorithms for some combinatorial optimization problems—streaming or otherwise.

In the maximum matching problem, edges of the input graph arrive one-by-one in the stream and the goal is to compute a matching of large size. Weighted matching is a well-studied generalization of maximum matching where the graph is edge-weighted, and, in a further generalization, a submodular function is defined on the edges. Submodular functions have received a lot of attention in theoretical computer science as well as, more recently, in machine learning.

I will discuss a reduction from submodular matching to weighted matching that also extends to streaming algorithms for very general constraints such as matroids. I will conclude with an overview of my other research.

Speaker Profile:

Sagar Kale did his Ph.D. at Dartmouth College where his advisor was Prof. Amit Chakrabarti. He is currently a postdoc at EPFL where his host is Prof. Ola Svensson. His research is mainly on streaming algorithms for combinatorial optimization problems related to matchings and matroids—which are fundamental structures in computer science.

Dates:
Friday, 18th October 2019 14:00-15:00