How fast can we solve or approximate classic problems that are known to admit a polynomial time solution? Often times the existing polynomial time algorithms are slow for practical applications. Fine-grained algorithm design aims to better understand the computational complexity of these problems and illustrates tradeoffs between the runtime of the algorithms and the quality of their solutions.

In this talk, I will present my work on classic and fundamental problems in fine-grained complexity including edit distance, longest common subsequence, pattern matching, longest increasing subsequence, and knapsack. In particular, my talk will cover an algorithm that approximates edit distance within a constant factor in truly subquadratic time. This answers a well-known question in combinatorial pattern matching.