Derandomizing Isolation Lemma: A Geometric Approach

Ramprasad Saptharishi
Tuesday, 1 Aug 2017, 16:00 to 17:00
A-201 (STCS Seminar Room)
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).