BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/742
DTSTAMP:20230914T125936Z
SUMMARY:A Fine-Grained Approach for Designing (Time and Space) Efficient Al
 gorithms
DESCRIPTION:Speaker: Rajesh Chitnis (Weizmann Institute of Science\nFaculty
  of Mathematics and Computer Science\n234 Herzl St.\, Rehovot 7610001\nIsr
 ael)\n\nAbstract: \nThe classical approach for designing algorithms measur
 es the time complexity only as a measure of the input size. In the 90's\, 
 Downey and Fellows proposed a fine-grained approach for NP-hard problems: 
 one or more parameters of the input instance are defined\, and we investig
 ate the effect of these parameters on the running time. The goal is to des
 ign algorithms that work efficiently if the parameters of the input instan
 ce are small\, even if the size of the input is large. Formally\, a proble
 m is said to be fixed-parameter tractable (FPT) with respect to parameter 
 $k$ if the problem can be solved in time $f(k)$·$n^{O(1)}$ where f is a c
 omputable function and n is the input size.\n\nIn the first part of the ta
 lk\, I will give a brief overview of FPT algorithms. This active area of r
 esearch has seen many new developments over the last few years. The standa
 rd techniques for designing FPT algorithms on undirected graphs such as bi
 dimensionality\, treewidth-based dynamic programming\, etc. seem to break 
 down for directed graphs. I will present some of my work which overcomes t
 his barrier\, and designs optimal FPT and XP algorithms for cut and connec
 tivity problems on directed graphs.\n\nThe second part of the talk will be
  about some recent work on parameterized streaming algorithms. For the Max
 imum Matching problem\, I will describe optimal streaming algorithms in va
 rious streaming models such as insertion-only\, promised and general inser
 tion-deletion.\n
URL:https://www.tcs.tifr.res.in/web/events/742
DTSTART;TZID=Asia/Kolkata:20170110T160000
DTEND;TZID=Asia/Kolkata:20170110T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR