BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/696
DTSTAMP:20230914T125934Z
SUMMARY:New Parallel Algorithm for Bipartite Matching
DESCRIPTION:Speaker: Tulasi mohan Molli\n\nAbstract: \nIn this talk we will
see an efficient parallel algorithm for the Bipartite Perfect Matching pr
oblem (BPM) due to Fenner\, Gurjar and Thierauf. The Perfect Matching prob
lem (PM) is to decide whether a given graph has a perfect matching. Edmond
s gave a polynomial time algorithm for the Perfect Matching problem in 196
5. However its parallel complexity is still not completely resolved as of
today. Fenner et al. showed that BPM can be solved using uniform circuits
of quasi-polynomial size n^O(log n)\, and O(log^2 n) depth where n is the
number of vertices in the input graph. Previously only an exponential uppe
r bound was known on the size of such circuits with poly-logarithmic depth
. The result of Ferner et al. is essentially a derandomization of the Isol
ation lemma based randomized algorithm due to Mulmuley\, Vazirani and Vazi
rani. We will also see an elegant proof of the Isolation Lemma due to Noam
Tashma.\n
URL:https://www.tcs.tifr.res.in/web/events/696
DTSTART;TZID=Asia/Kolkata:20160708T160000
DTEND;TZID=Asia/Kolkata:20160708T173000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR