Tata Institute of Fundamental Research
Derandomizing the Isolation Lemma and Parallel Algorithms
STCS Seminar
Speaker:
Rohit Gurjar (California Institute of Technology
Center for the Mathematics of Information
1200 E California Blvd.
Pasadena, CA 91125
United States of America)
Organiser:
Ramprasad Saptharishi
Date:
Tuesday, 16 Jan 2018, 11:30 to 12:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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: | Rohit Gurjar (California Institute of Technology Center for the Mathematics of Information 1200 E California Blvd. Pasadena, CA 91125 United States of America) |
| Organiser: | Ramprasad Saptharishi |
| Date: | Tuesday, 16 Jan 2018, 11:30 to 12:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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).
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).