Conditional hardness of string similarity and tree similarity

18/01/2018 - 12:00

The theory of NP-hardness allows computer scientists to classify nearly all problems as polynomial-time solvable (in P) or NP-hard. Recently, there has been a similar development in classifying problems within the class P. These are known as conditional lower bounds, that is, they depend on the conjectured hardness of certain archetypal problems such as CNF Satisfiability and all-pairs shortest paths (APSP). Proving conditional lower bounds for fundamental problems in P is now a flourishing research area with the goal of better understanding the landscape of P. Most of the problems for which conditional lower bounds were recently shown are Stringology problems.  


In my talk I will focus on the problems of computing the edit distance of strings and the edit distance of trees. I will first show that these problems are very similar in terms of their upper bounds by showing that their state of the art algorithm is in fact the same algorithm. Its running time for strings is O(n^2) and for trees is O(n^3). Then, I will show that in terms of lower bounds the problems are in fact very different: String edit distance exhibits the hardness of the strong exponential time hypothesis (asserting that CNF Satisfiability requires O(2^n) time) while tree edit distance exhibits the hardness of the ASPS hypothesis (asserting that APSP requires O(n^3) time).