Seminars

View all Seminars  |  Download ICal for this event

Bipartite Matching is in NC

Series: Bangalore Theory Seminars

Speaker: Rohit Gurjar, Indian Institute of Technology Bombay

Date/Time: Jun 23 16:00:00

Location: Online Talk (See Teams link below)

Abstract:
We give an NC algorithm for deciding if a given bipartite graph has a perfect matching. The algorithm and its proof are based on the polynomial method, inspired from the idea of subspace design (Guruswamy and Kopparty, Combinatorica 2016). We also generalize this result to weighted bipartite matching and computation of non-commutative rank.


Microsoft Teams link:

Link


We are grateful to the Kirani family (Link and the Walmart Center for Tech Excellence (Link for generously supporting this seminar series


Hosts: Rameesh Paul, Debajyoti Kar, KVN Sreenivas, Nirjhar Das, Rahul Madhavan