Sublinear Algorithms for Gap Edit Distance
Offered By: IEEE via YouTube
Course Description
Overview
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
Taught by
IEEE FOCS: Foundations of Computer Science
Tags
Related Courses
An Improved Exponential-Time Approximation Algorithm for Fully-Alternating Games Against NatureIEEE via YouTube Computation in the Brain Tutorial - Part 2
IEEE via YouTube Computation in the Brain - Part 1
IEEE via YouTube Spectral Independence in High-Dimensional Expanders and Applications to the Hardcore Model
IEEE via YouTube Cookbook Lower Bounds for Statistical Inference in Distributed and Constrained Settings - Part 1
IEEE via YouTube