BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1601
DTSTAMP:20250731T071153Z
SUMMARY:Counting in constrained worlds and the Fibonacci Trick
DESCRIPTION:Speaker: Aindrila Rakshit (TIFR)\n\nAbstract: \nMany graph-theo
 retic counting problems remain intractable (indeed #P-complete) despite ad
 ditional constraints on their structural properties\, like planarity\, bip
 artiteness\, and low degree\, even though their decision counterparts migh
 t be easy. This talk explores Salil Vadhan’s framework for proving #P-co
 mpleteness of problems like #Matchings\, #VertexCovers\, and #Monotone2CNF
  even on planar\, low-degree\, and regular graphs. A new interpolation bas
 ed reduction technique that uses Fibonacci-style gadgets to preserve struc
 ture like constant degree\, during reductions is used to prove these resul
 ts. Based on: The Complexity of Counting in Sparse\, Regular\, and Planar 
 Graphs\, Salil P. Vadhan (https://doi.org/10.1137/S0097539797321602).\n \
 n
URL:https://www.tcs.tifr.res.in/web/events/1601
DTSTART;TZID=Asia/Kolkata:20250801T160000
DTEND;TZID=Asia/Kolkata:20250801T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR