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