Sublinear Algorithms for Gap Edit Distance

Explore the concept of gap edit distance and its sublinear algorithms in this 21-minute IEEE conference talk. Delve into the topic with speakers Elazar Goldenberg, Robert Krauthgamer, and Barna Saha as they cover key aspects such as dynamic programming, approximation techniques, and sublinear time complexity. Learn about distance results, compare simple and linear algorithms, and understand the challenges associated with possible matching shifts and period shifts. Gain insights into the keylemmata and main theorem that underpin this fascinating area of computational theory.