Title: Derandomizing the Isolation Lemma and Parallel algorithms

Description: Speaker: Dr. Rohit Gurjar

Time: Thursday, 18 January 2018, 10:30am
Venue: CC 109 Room, 01st Floor, New CSE Bldg.

To understand the power of randomization is one of the fundamental questions in theoretical computer science. In particular, we want to know if every problem with an efficient randomized algorithm also has a deterministic one, without much loss in efficiency. One of the widely used tools in randomized algorithms is the Isolation Lemma of Mulmuley-Vazirani-Vazirani. It states that for any family of subsets of a set, if the each element of the set is assigned a random weight from a small range, then with high probability the family has a unique minimum weight set. One of the many applications of the Isolation lemma is a randomized parallel algorithm for the perfect matching problem.
Derandomizing the Isolation lemma, that is, to deterministically construct weights with the isolating property, has been an interesting open question. In a series of works, we derandomized the isolation lemma for many interesting families of sets. Among many implications of these results are deterministic parallel (quasi-NC) algorithms for bipartite matching and linear matroid intersection and, a solution to some polynomial identity testing questions. The most general setting where our technique works is when the polytope corresponding to the family has all its faces defined by totally unimodular equations. The talk will give an overview of these results and some possible future directions.
Based on joint works with Stephen Fenner, Thomas Thierauf, and, Nisheeth Vishnoi.

Speaker Profile:
Information about Dr. Rohit Gurjar is available at: https://www.cse.iitk.ac.in/users/rgurjar/

California Institute of Technology

Prof. Nutan Limaye

Date: Thursday, 18 January, 2018
Time: 10:30am IST
Access: Public
Category: Talk*
Created by: Department Calendar
Updated: Sunday, 11 November, 2018 11:45am IST
Send Reminder: Yes  -  162 hours 5 minutes before start
Participants: Department Calendar
<office@cse.iitb.ac.in> (External User)
<seminar@iitb.ac.in> (External User)
_NUC_department <all@cse.iitb.ac.in> (External User)