Online List Labeling - Breaking the Log^2 N Barrier

Online List Labeling - Breaking the Log^2 N Barrier

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.