BARC talk by Rohit Gurjar
Tuesday, August 4, 2026, 14:00-15:00, Rohit Gurjar, faculty member in the CSE department at IIT Bombay, India, will be giving a BARC talk on "A deterministic parallel algorithm for bipartite matching" at the IT University. After a short break, a technical deep dive will follow from 15:15 - 17:00 at the same location.
Abstract:
The bipartite matching problem is one of the most extensively studied problems in algorithms and complexity theory. Beyond numerous practical applications such as assigning suitable tasks to machines, its study has led to several influential ideas in the field. In this talk, we will review the history of the problem from the perspective of parallel algorithms and discuss a recent result that gives the first deterministic parallel algorithm for it, settling a question that had remained open for more than four decades. In the later part of the talk, we will discuss the complete proof details and mention the extensions of the result which use the same techniques.
Rohit Gurjar is a faculty member in the CSE department at IIT Bombay since 2018. His research interests center on theoretical computer science, specifically Computational Complexity, Derandomization, Polyhedral Combinatorics, and Parallel Complexity. In particular, he has worked on the polynomial identity testing, bipartite matching and related combinatorial problems. Before joining IITB, he did his postdocs at the University of Ulm (Germany), Tel Aviv University (Israel), and Caltech (USA), and obtained his Ph.D. from IIT Kanpur.
Host:
Nutan Limaye