The theory of NP-hardness has been remarkably successful in identifying problems that are unlikely to be solvable in polynomial time. However, many other important problems do have polynomial-time algorithms, but large exponents in their runtime bounds often make them inefficient in practice. For example, quadratic-time algorithms, although practical on moderately sized inputs, can become inefficient on big data problems that involve gigabytes of data or more. While for many problems no sub-quadratic time algorithms are known, any evidence of quadratic-time hardness has remained elusive.

 

In this talk I will give an overview of recent research that aims to remedy this situation. In particular, I will focus on the class of problems involving similarity measures between sequences, such as Edit Distance, Frechet Distance and Dynamic Time Warping. These problems have classic quadratic time solutions based on dynamic programming. However, despite extensive amount of research, no strongly sub-quadratic algorithms for these problems are known for general inputs. I will show that, under a natural complexity-theoretic conjecture, such sub-quadratic algorithms do not exist. Specifically, I will show that strongly sub-quadratic algorithms for any of those problems would violate the Strong Exponential Time Hypothesis (SETH), which postulates (roughly) that satisfiability over n variables cannot be solved in c^n time for c<2.

 

This talk covers results from several papers, by Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Kunnemann, Virginia Vassilevska Williams and the speaker.