Seminar: Edit Distance to Clustering: A Fine-Grained Approach to Approximation Algorithms
Debarati Das
Emmert H. Bashore Faculty Development Assistant Professor
Department of Computer Science and Engineering
Pennsylvania State University
Thursday, January 23
9:30 - 10:30AM
1100 Torgersen Hall
Abstract
Tractable problems are traditionally defined as those solvable in polynomial time. However, with the exponential growth of data in modern applications, even polynomial-time algorithms may no longer be considered efficient. Recent years have witnessed significant developments in understanding the complexity landscape within the polynomial-time regime through the lens of fine-grained complexity. This framework enables to classify problems that are unlikely to admit faster solutions than those currently known, based on strong complexity assumptions such as the Strong Exponential Time Hypothesis (SETH), All-Pairs Shortest Paths (APSP), Orthogonal Vectors (OV), and 3-SUM.
Approximation algorithms play a pivotal role in circumventing these hardness barriers for both intractable and fine-grained hard problems. In my talk, I will discuss recent advances in approximation algorithms for problems related to edit distance and clustering. I will highlight the connections between a variety of problems involving edit distance and its variants, as well as clustering under these measures. By leveraging unifying strategies, we will examine how efficient approximation algorithms can be developed to tackle these challenges effectively. Additionally, I will outline future directions, key barriers, and potential strategies for progressing toward optimal solutions in this domain.
Biography
Debarati Das is the Emmert H. Bashore Faculty Development Assistant Professor in the Department of Computer Science and Engineering at the Pennsylvania State University. Her primary research area is theoretical computer science, with a focus on fine-grained complexity, and approximation algorithms. Her work has been published in top-tier theoretical computer science conferences, including STOC, FOCS, and SODA. She is the recipient of the prestigious FOCS Best Paper Award (2018) and the NSF CAREER Award (2024).
Before joining Penn State, Debarati was a postdoctoral researcher at the Basic Algorithms Research Copenhagen (BARC), Copenhagen. She completed her Ph.D. from Charles University, Prague. She is also a member of the TCS for All, an organization dedicated to promoting the inclusion and participation of underrepresented students in theoretical computer science by providing travel scholarships and outreach initiatives.