« Online List Labeling: Breaking the log^2 n Barrier
Online List Labeling: Breaking the log^2 n Barrier
April 27, 2022, 11:00 AM - 12:00 PM
Location:
Online Event
Nicole Wein, DIMACS
The online list labeling problem is a basic primitive in data structures. The goal is to store a dynamically-changing set of n items in an array of m slots, while keeping the elements in sorted order. To do so, some items may need to be moved over time, and the goal is to minimize the number of items moved per insertion/deletion. When m = Cn for some constant C>1, an upper bound of O(log^2 n) items moved per insertion/deletion has been known since 1981. There is a matching lower bound for deterministic algorithms, but for randomized algorithms, the best known lower bound is Omega(log n), leaving a gap between upper and lower bounds. We improve the upper bound, providing a randomized data structure with expected O(log^{3/2} n) items moved per insertion/deletion.
Joint work with Michael Bender, Alexander Conway, Martin Farach-Colton, Hanna Komlos, and William Kuszmaul
Special Note: The Theory of Computing Seminar is being held online. Contact the organizers for the link to the seminar.