Abstract: Edit distance is a fundamental measure of sequence similarity. However, for two strings of length n, exact computation of edit distance requires time quadratic in n which is prohibitive for large data sets. This has resulted in a sequence of recent results that try to design faster algorithms for edit distance allowing for an approximate solution. Can one design any reasonable approximation algorithms for edit distance in time that is sublinear in n? This is of course very challenging. However, recently some progress has been made on this front. In this presentation, I will cover some of our recent works on sublinear time algorithm design for edit distance.

Based on joint works with Elazar Godenberg, Tomasz Kociumaka, Robert Krauthgamer, and Aviad Rubinstein.

Bio: Barna Saha is a Jacob Faculty Scholar and an Associate Professor of Computer Science and Engineering & Halıcıoğlu Data Science Institute at UCSD. Before coming to UCSD,  she has held faculty positions at UC Berkeley, and University of Massachusetts Amherst as well as senior research scientist position at the AT&T Shannon Research Laboratory. Her research interest spans algorithm design and analysis, probabilistic methods, and databases. She is a recipient of the 

Presidential Early Career Awards for Scientists and Engineers (PECASE), Sloan Fellowship, NSF CAREER Award, Young Alumnus Award (IIT Kanpur), Google and Yahoo faculty awards, and has been recognized as a Kavli fellow from the National Academy of Sciences.