BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1671
DTSTAMP:20260116T054445Z
SUMMARY:Fast exact algorithms via the Matrix Tree Theorem
DESCRIPTION:Speaker: Shanthanu S. Rai (TIFR)\n\nAbstract: \nCounting Hamilt
 onian paths in graphs and perfect matchings in bipartite graphs are well k
 nown hard problems. In this talk\, we will use a seemingly innocuous resul
 t to provide the best known upper bounds for these two hard to compute obj
 ects\, along with some of their restrictions and variants. The result we u
 se is the so called Matrix Tree Theorem\, which counts the number of spann
 ing trees in the graph by reducing it to a single determinant computation.
 If time permits\, we will also see fast exact algorithms for finding Hamil
 tonian paths in bipartite graphs. For all of the algorithms\, we will see 
 a common recipe using the Matrix Tree Theorem.Paper link: https://arxiv.o
 rg/pdf/2512.08600\n
URL:https://www.tcs.tifr.res.in/web/events/1671
DTSTART;TZID=Asia/Kolkata:20260116T160000
DTEND;TZID=Asia/Kolkata:20260116T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR