School of Technology and Computer Science Seminars

Derandomizing Isolation Lemma: A Geometric Approach

by Rohit Gurjar (Tel Aviv University, Israel)

Tuesday, August 1, 2017 from to (Asia/Kolkata)
at A-201 (STCS Seminar Room)
Description
We present a geometric approach towards derandomizing the Isolation lemma for a given family, i.e., deterministically constructing a weight assingnment which ensures a unique minimum weight set in the family. The idea is to work with a polytope corresponding to the family of sets. In this talk, we present the approach in terms of general polytopes and describe a sufficient condition on the polytope for this approach to work. The approach gives a quasi-polynomially bounded weight assignment. Finally, we show that two specific families - perfect matchings in bipartite graphs and common base sets of two matroids - satisfy the required condition and thus, we get an isolating weight assignment for these cases. This also puts the two problems in quasi-NC (based on joint works with Stephen Fenner and Thomas Thierauf).