Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

Edit Distance in Near-Linear Time - It’s a Constant Factor

IEEE via YouTube

Overview

Explore a groundbreaking approach to computing edit distance in near-linear time through this 26-minute IEEE conference talk by Columbia University researchers Alexandr Andoni and Negev Shekel Nosatzki. Delve into the problem setup, potential solutions, and the innovative approach that achieves this computational feat. Gain insights into the underlying data structure and its guarantees, understanding why this method works and its implications for algorithmic efficiency.

Syllabus

Introduction
Problem set up
What can be done
Approach
Why
Solution
Data Structure
Guarantees

Taught by

IEEE FOCS: Foundations of Computer Science

Reviews

Start your review of Edit Distance in Near-Linear Time - It’s a Constant Factor

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.