ICS 269, Spring 2022: Theory Seminar
Online through Zoom (link TBA), 1:00 – 1:50

8 April 2022: Hanna Komlós

Online list labeling: breaking the ${\log }^{2}n$ barrier

The online list-labeling problem is an algorithmic primitive with a large literature of upper bounds, lower bounds, and applications. The goal is to store a dynamically-changing set of $n$ items in an array of $m$ slots, while maintaining the invariant that the items appear in sorted order, and while minimizing the relabeling cost, defined to be the number of items that are moved per insertion/deletion. For the linear regime, where $m=(1+\mathrm{\Theta }(1))n$, an upper bound of $O({\log }^{2}n)$ on the relabeling cost has been known since 1981. A lower bound of $\mathrm{\Omega }({\log }^{2}n)$ is known for deterministic algorithms and for so-called smooth algorithms, but the best general lower bound remains $\mathrm{\Omega }(\log n)$. The central open question in the field is whether $O({\log }^{2}n)$ is optimal for all algorithms.

In this paper, we give a randomized data structure that achieves an expected relabeling cost of $O({\log }^{3/2}n)$ per operation. More generally, if $m=(1+\epsilon )n$ for $\epsilon =O(1)$, the expected relabeling cost becomes $O({\epsilon }^{-1}{\log }^{3/2}n)$. Our solution is history independent, meaning that the state of the data structure is independent of the order in which items are inserted/deleted. For history-independent data structures, we also prove a matching lower bound: for all $\epsilon$ between $1/n^{1/3}$ and some sufficiently small positive constant, the optimal expected cost for history-independent list-labeling solutions is $\mathrm{\Theta }({\epsilon }^{-1}{\log }^{3/2}n)$.