Tata Institute of Fundamental Research
Derandomizing Isolation Lemma: A Geometric Approach
STCS Seminar
Speaker:
Rohit Gurjar (Tel Aviv University
Department of Computer Science
Tel Aviv-Yafo
Israel)
Organiser:
Ramprasad Saptharishi
Date:
Tuesday, 1 Aug 2017, 16:00 to 17:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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).
| Speaker: | Rohit Gurjar (Tel Aviv University Department of Computer Science Tel Aviv-Yafo Israel) |
| Organiser: | Ramprasad Saptharishi |
| Date: | Tuesday, 1 Aug 2017, 16:00 to 17:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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).