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.
Saeed Seddighin is currently a Research Assistant Professor at TTIC. He was a postdoc at Harvard University hosted by Prof. Michael Mitzenmacher and received his PhD in 2019 from the University of Maryland under Prof. MohammadTaghi Hajiaghayi.
He has a broad interest in theoretical computer science and its applications in computational biology, machine learning, economics, and artificial intelligence. The emphasis of his research is on fine-grained algorithm design and algorithmic game theory.