BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1715
DTSTAMP:20260519T045914Z
SUMMARY:FPT-Approximation via Random Walks
DESCRIPTION:Speaker: Tanmay Inamdar (IIT Jodhpur)\n\nAbstract: \nWe present
  a simple viewpoint for designing time-ratio trade-offs for classical fixe
 d-parameter tractable (FPT) optimization problems. At the heart of this ap
 proach is a randomized version of a natural "exact branching" algorithm\, 
 where each branch is explored with a carefully tuned probability. The appr
 oximation guarantee and its corresponding success probability of the resul
 ting randomized branching algorithm can be analyzed by modeling the behavi
 or as a random walk on a suitably defined state space. We illustrate the 
 approach using Vertex Cover\, using both the standard parameterization by 
 solution size\, and then by the gap between optimum integral and LP soluti
 ons. As a corollary\, we also obtain time-ratio trade-offs for other prob
 lems of interest\, including Odd Cycle Transversal\, and Almost 2-SAT.\n 
 \nThis talk is based on a paper with Ishan Chakraborty\, Ariel Kulik\, Mad
 humita Kundu\, and Saket Saurabh that is to appear in STOC 2026.\n
URL:https://www.tcs.tifr.res.in/web/events/1715
DTSTART;TZID=Asia/Kolkata:20260526T160000
DTEND;TZID=Asia/Kolkata:20260526T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR