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.

Syllabus

Introduction
Definition
Example
Dynamic Programming
Approximation
Sublinear Time
Distance
Results
Comparison
Simple Algorithm
Linear Algorithm
Possible Matching Shift
Period Shift
Keylemma
Challenges
Main Theorem