CSE Colloquium: Fine-grained Approximation Algorithms for String Similarity

Zoom Information: Join from PC, Mac, Linux, iOS or Android: https://psu.zoom.us/j/97464641322?pwd=eUNsTFhUZnFVR1dudnNkUHowcnBqUT09 Password: 489880 

Or iPhone one-tap (US Toll): +13017158592,97464641322# or +13126266799,97464641322# 

Or Telephone: Dial: +1 301 715 8592 (US Toll) +1 312 626 6799 (US Toll) +1 646 876 9923 (US Toll) +1 253 215 8782 (US Toll) +1 346 248 7799 (US Toll) +1 669 900 6833 (US Toll) Meeting ID: 974 6464 1322 Password: 489880 International numbers available: https://psu.zoom.us/u/aeFaW83LAx 

ABSTRACT: Recent years have seen a surge of methods for analyzing the complexity landscape within the polynomial-time regime. Through the lens of fine-grained complexity, we are able to classify which problems are unlikely to have faster solutions than currently known under some strong complexity assumptions like Strong Exponential Time Hypothesis (SETH), All-Pairs Shortest Path (APSP), Orthogonal Vectors (OV), 3-SUM, etc. 

Approximation algorithms are useful for escaping these hardness barriers. In this talk, I will discuss the recent advances in fine-grained approximation algorithms with a special focus on problems related to string similarity. I will also explain the algorithm computing a constant approximation of edit distance in truly sub-quadratic time. 

BIOGRAPHY: Debarati is a postdoctoral researcher at Basic Algorithms Research Copenhagen (BARC) hosted by Prof. Mikkel Thorup. 

Prior to this, she completed her PhD. from the Computer Science Institute of Charles University, Prague under the guidance of Prof. Michal Koucky. Her work '' Approximating Edit Distance within Constant Factor in Truly Sub-Quadratic Time'' won the best paper award at FOCS 2018. 

Her research interest lies in theoretical computer science with a special focus on fine-grained complexity, string algorithms, randomized algorithms, clustering algorithms and graph algorithms.