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