Loading Events

« All Events

  • This event has passed.

CIS Seminar: “Modern Fine-grained Algorithms for Classic Problems”

February 22 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.

Details

Date:
February 22
Time:
3:30 PM - 4:30 PM
Event Tags:
Website:
https://www.cis.upenn.edu/events/

Organizer

Computer and Information Science
Phone:
215-898-8560
Email:
cis-info@cis.upenn.edu
View Organizer Website

Venue

Wu and Chen Auditorium (Room 101), Levine Hall
3330 Walnut Street
Philadelphia, PA 19104 United States
+ Google Map
View Venue Website