- This event has passed.
CIS Seminar: “Modern Fine-grained Algorithms for Classic Problems”
February 22, 2022 at 3:30 PM - 4:30 PM
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.
Saeed Seddighin
Research Assistant Professor, Toyota Technological Institute at Chicago
Saeed Seddighin is currently a Research Assistant Professor at the Toyota Technological Institute at Chicago. Prior to joining TTIC, he was a postdoc at Harvard University hosted by Prof. Michael Mitzenmacher. Saeed 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.