Modern Fine-grained Algorithms for Classic Problems

How fast can we solve or approximate classic problems that are known to admit a polynomial time solution? With the ever-growing volume of data in today's world, many of 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. I will also discuss several big data algorithms that can be developed with the same techniques.