CMI Seminar

Tuesday October 31, 2017 4:00 PM

Derandomization: Polynomial Identity Testing and Isolation Lemma (2nd of 2 parts)

Speaker: Rohit Gurjar, CMS, Caltech
Location: Annenberg 314

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.

Series Center for the Mathematics of Information Seminar Series

Contact: Linda Taddeo at 626-395-6704 ltaddeo@caltech.edu
For more information visit: http://www.cmi.caltech.edu/events.shtml