Login
Talks & Seminars
Title: Derandomizing Isolation Lemma: A geometric approach
Dr. Rohit Gurjar, Tel Aviv University
Date & Time: July 31, 2017 14:00
Venue: Conference Room, C Block, 01st Floor, Department of Computer Science and Engineering, Kanwal Rekhi (KReSIT) Building
Abstract:
We present a geometric approach towards derandomizing the Isolation lemma for a given family of subsets, i.e., deterministically constructing a weight assignment 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 Profile:
[2010-15] PhD Student at CSE, IIT Kanpur (Supervisors: Dr. Manindra Agrawal and Dr. Nitin Saxena) PhD Thesis [2005-10] B.Tech. & M.Tech. Dual Degree at CSE, IIT Kanpur (Supervisor: Dr. Piyush Kurur ) M.Tech. Thesis. [2015-16] Postdoctoral Fellow at University of Ulm (with Thomas Thierauf) [2016- ] Postdoctoral Fellow in Theory of Computation Group at Tel Aviv University (with Amir Shpilka) Homepage: https://www.cse.iitk.ac.in/users/rgurjar/
List of Talks

Webmail

Username:
Password:
Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback