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.