Abstract

We will discuss a SETH-based lower bound for the longest common subsequence problem that matches the simple quadratic time dynamic programming solution. Beyond the simple algorithm, longest common subsequence has a rich literature on special cases, more precisely, on algorithms that are fast when certain input parameters are small. We show how to extend the conditional lower bounds to this parameterized setting. This is joined work with Marvin Künnemann.

Video Recording