BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/797
DTSTAMP:20230914T125938Z
SUMMARY:Derandomizing Isolation Lemma: A Geometric Approach
DESCRIPTION:Speaker: Rohit Gurjar (Tel Aviv University\nDepartment of Compu
ter Science\nTel Aviv-Yafo\nIsrael)\n\nAbstract: \nWe present a geometric
approach towards derandomizing the Isolation lemma for a given family\, i.
e.\, deterministically constructing a weight assingnment which ensures a u
nique minimum weight set in the family. The idea is to work with a polytop
e corresponding to the family of sets. In this talk\, we present the appro
ach in terms of general polytopes and describe a sufficient condition on t
he polytope for this approach to work. The approach gives a quasi-polynomi
ally bounded weight assignment. Finally\, we show that two specific famili
es - perfect matchings in bipartite graphs and common base sets of two mat
roids - satisfy the required condition and thus\, we get an isolating weig
ht assignment for these cases. This also puts the two problems in quasi-NC
(based on joint works with Stephen Fenner and Thomas Thierauf).\n
URL:https://www.tcs.tifr.res.in/web/events/797
DTSTART;TZID=Asia/Kolkata:20170801T160000
DTEND;TZID=Asia/Kolkata:20170801T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR