Barna Saha: Space & Time Efficient Algorithms for "Bounded Difference" Problems

Speaker: Barna Saha, UMass Amherst

Date: Tuesday, December 12, 2017

Time: 4:00 PM to 5:00 PM Note: all times are in the Eastern Time Zone

Refreshments: 3:45 PM

Public: Yes

Location: Patil/Kiva G449

Event Type: Seminar

Room Description:

Host: Virginia Vassilevska Williams

Contact: Deborah Goodwin, 617.324.7303,

Relevant URL:

Speaker URL:

Speaker Photo:
Barna 2014

Reminders to:,

Reminder Subject: TALK: Barna Saha: Space & Time Efficient Algorithms for "Bounded Difference" Problems

Abstract: Many fundamental sequence problems exhibit "bounded difference property", that is whenever the input changes slightly, the change in the output is also bounded. Some examples include the longest increasing subsequence problem (studied since Schensted, 1961), the string edit distance computation (studied since Levenshtein, 1965), the language edit distance problem (studied since Aho and Peterson, 1972), RNA Folding (studied since Jacobson and Nussinov, 1980) etc. For all these problems, there exist simple polynomial time algorithms based on dynamic programming.

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 or space complexity of bounded difference problems allowing for additive approximations. For some of these problems, it is also possible to design an exact algorithm that runs faster than the corresponding dynamic programming using a reduction to bounded-difference (min,+)-matrix multiplication. Time permitting, I will discuss how this raises serious doubts to the All Pairs Shortest Path conjecture which is the cornerstone to show cubic-hardness of a large collection of fundamental graph and matrix problems.

The talk is mainly based on my FOCS 2017 paper and will also allude to a joint work with Karl Bringmann, Fabrizio Grandoni and Virginia Vassilevska Williams that appeared in FOCS 2016.

Research Areas:

Impact Areas:

See other events that are part of the Theory of Computation (TOC) 2017.

Created by Deborah Goodwin Email at Wednesday, December 06, 2017 at 11:17 AM.