Please note: This seminar will take place in DC 2568 and online.
Hanna Komlós, PhD student
Tandon School of Engineering, New York University
The list-labeling problem captures the basic task of storing a dynamically changing set of up to N elements in sorted order in an array of size M=cN where c is a constant. The goal is to support insertions and deletions while moving around elements within the array as little as possible. Until recently, the best known upper bound stood at O(log^2(N)) amortized cost. This bound, which was first established in 1981, was finally improved two years ago, when a randomized O(log^{1.5}(N)) expected-cost algorithm was discovered. The best randomized lower bound for this problem remains Ω(log(N)), and closing this gap is considered to be a major open problem in data structures.
We present the See-Saw Algorithm, a randomized list-labeling solution that achieves a nearly optimal bound of O(log(N) polyloglog(N)) amortized expected cost. This bound is achieved despite at least three lower bounds showing that this type of result is impossible for large classes of solutions.
This work will appear at FOCS 2024.
To attend this seminar in person, please go to DC 2568. You can also attend virtually using Zoom.