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

YouTube

Online List Labeling - Breaking the Log^2 N Barrier

Simons Institute via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
Explore a groundbreaking lecture on the online list labeling problem, a fundamental concept in data structures. Delve into the challenge of storing a dynamically-changing set of n items in an array of m slots while maintaining sorted order. Learn about the historical O(log^2 n) upper bound for item movements per insertion/deletion and the existing gap between upper and lower bounds for randomized algorithms. Discover a new randomized data structure that achieves an expected O(log^{3/2} n) items moved per operation, breaking the long-standing log^2 n barrier. Gain insights into the collaborative research behind this advancement in dynamic graphs and algorithm design.

Syllabus

Online List Labeling: Breaking the log^2 n Barrier

Taught by

Simons Institute

Reviews

Start your review of Online List Labeling - Breaking the Log^2 N Barrier

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.