BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1759
DTSTAMP:20260821T100846Z
SUMMARY:Exponential Lower Bounds for the Pfaffian Number of Graphs
DESCRIPTION:Speaker: Ranveer Singh (IIT Indore)\n\nAbstract: \nThe FKT algo
 rithm counts perfect matchings in planar graphs using a single Pfaffian. F
 or graphs embedded on an orientable surface of genus g\, Galluccio–Loebl
  and Tesler showed that the perfect-matching polynomial can be expressed u
 sing at most 4^g Pfaffians. We prove that an exponential dependence on g i
 s unavoidable: for every g>=1\, there exists a graph of genus at most g wh
 ose perfect-matching polynomial requires at least (8/3)^g Pfaffians. We pr
 ove this by showing that expressing the permanent of a matrix as a linear 
 combination of determinants of the same size signed matrices requires an e
 xponential number of terms.  \n \nBio:  Prof. Ranveer Singh is an Asso
 ciate Professor in the Department of Computer Science and Engineering at I
 IT Indore. He received his B.Tech and Ph.D. from IIT Jodhpur and was a pos
 tdoctoral fellow at the Technion–Israel Institute of Technology. His res
 earch interests include algebraic graph theory and the permanent vs determ
 inant question. \n
URL:https://www.tcs.tifr.res.in/web/events/1759
DTSTART;TZID=Asia/Kolkata:20260901T160000
DTEND;TZID=Asia/Kolkata:20260901T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR