Date & Time: Tuesday, February 16, 2016, 14:00-15:30
Venue: Ramanujan Hall
Title:A derandomization of Lovasz's algorithm for Perfect Matching
Speaker: Srikanth Srinivasan, Mathematics Department, IIT Bombay
Abstract: In 1979, Lovasz gave a beautiful simple *randomized* algorithm to detect if a given bipartite graph has a perfect matching, which involves computing the determinant of the Tutte matrix of the graph at a randomly chosen point. The algorithm has the additional advantage of being easily parallelizable. The problem of coming up with a deterministic version of this algorithm remained open for over 35 years until it was solved in 2015 by Rohit Gurjar, Stephen Fenner and Thomas Thierauf. We will see this algorithm.