Derandomizing Isolation Lemma: A Geometric Approach

Speaker: 

Rohit Gurjar

Affiliation: 

Tel Aviv University
Department of Computer Science
Tel Aviv-Yafo
Israel

Time: 

Tuesday, 1 August 2017, 16:00 to 17:00

Venue: 

Organisers: 

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