BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1524
DTSTAMP:20250130T084500Z
SUMMARY:Bipartite Perfect Matching is in Quasi-NC
DESCRIPTION:Speaker: Soham Chatterjee (TIFR)\n\nAbstract: \nIn this talk\, 
 I will explain the Isolation lemma introduced by Mulmuley\, Vazirani\, Vaz
 irani in [MVV87] and use it to get an upper bound on the parallel complexi
 ty of bipartite perfect matching. The Isolation lemma has also been instru
 mental in the design of randomized algorithms and has contributed to sever
 al significant complexity upper bounds.\nI will present a parallel algorit
 hm for bipartite matching achieved through the derandomization of the isol
 ation lemma. This result demonstrates that the bipartite perfect matching 
 problem lies in $Quasi-NC^2$.\nThe talk will be based on the paper "Bipart
 ite Perfect Matching is in quasi-NC" by Fenner\, Gurjar and Thierauf.\n
URL:https://www.tcs.tifr.res.in/web/events/1524
DTSTART;TZID=Asia/Kolkata:20250131T160000
DTEND;TZID=Asia/Kolkata:20250131T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR