CMI Seminar

Derandomization is one of the central questions in theory of computing. The question asks if all problems with efficient randomized algorithms also have deterministic algorithms with comparable time complexity. The question also has connections with circuit lower bounds.
    One of the randomized solutions for PIT goes via the Isolation Lemma. The lemma states that given a family F of subsets of set E, assigning random weights to the elements of E ensures there is a unique minimum weight set in the family F.
    Derandomizing the Isolation Lemma means constructing such weights in a deterministic way. One of the many applications of PIT and Isolation Lemma is a randomized parallel algorithm for the graph matching problem. Recently, we gave a geometric approach for derandomizing the Isolation Lemma. Applying it to a specific case gives a deterministic parallel algorithm for bipartite matching.
    The first talk will give an introduction to these topics. In the second talk, I will describe our isolation approach which works for totally unimodular polytopes. I will end with an open question about short vectors in lattices, which tells in which all settings our isolation approach works.