**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.