BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
METHOD:PUBLISH
BEGIN:VTIMEZONE
TZID:America/New_York
BEGIN:DAYLIGHT
DTSTART:20180311T030000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
RRULE:FREQ=YEARLY;BYDAY=2SU;BYMONTH=3
TZNAME:EDT
END:DAYLIGHT
BEGIN:STANDARD
DTSTART:20171105T010000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
RRULE:FREQ=YEARLY;BYDAY=1SU;BYMONTH=11
TZNAME:EST
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTAMP:20220930T165503Z
UID:c8b4fd7c-3c9a-405d-add0-14504c0b7862
DTSTART;TZID=America/New_York:20171212T160000
DTEND;TZID=America/New_York:20171212T170000
CREATED:20171206T111714
DESCRIPTION: Abstract: Many fundamental sequence problems exhibit "bound
ed difference property"\, that is whenever the input changes slightly\, th
e change in the output is also bounded. Some examples include the longest
increasing subsequence problem (studied since Schensted\, 1961)\, the stri
ng edit distance computation (studied since Levenshtein\, 1965)\, the lang
uage edit distance problem (studied since Aho and Peterson\, 1972)\, RNA F
olding (studied since Jacobson and Nussinov\, 1980) etc. For all these pro
blems\, there exist simple polynomial time algorithms based on dynamic pro
gramming. \n\n\n Dynamic programming is one of the most systematic ways
of developing polynomial time algorithms\, but it often suffers from high
space and time complexity. In this talk\, I will show a simple technique
of amnesic dynamic programming using which we can improve either on time o
r space complexity of bounded difference problems allowing for additive ap
proximations. For some of these problems\, it is also possible to design a
n exact algorithm that runs faster than the corresponding dynamic programm
ing using a reduction to bounded-difference (min\,+)-matrix multiplication
. Time permitting\, I will discuss how this raises serious doubts to the A
ll Pairs Shortest Path conjecture which is the cornerstone to show cubic-h
ardness of a large collection of fundamental graph and matrix problems.\n\
n\n\n The talk is mainly based on my FOCS 2017 paper and will also allu
de to a joint work with Karl Bringmann\, Fabrizio Grandoni and Virginia Va
ssilevska Williams that appeared in FOCS 2016.\n\n
LAST-MODIFIED:20171206T113001
LOCATION:Patil/Kiva G449
SUMMARY:Barna Saha: Space & Time Efficient Algorithms for "Bounded Differen
ce" Problems
URL:https://calendar.csail.mit.edu/events/195843
END:VEVENT
END:VCALENDAR