  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 + \Theta(1)) n$, an upper bound of
$O(\log^2 n)$ on the relabeling cost has been known since 1981. A lower bound
of $\Omega(\log^2 n)$ is known for deterministic algorithms and for so-called
smooth algorithms, but the best general lower bound remains $\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
+ \varepsilon) n$ for $\varepsilon = O(1)$, the expected relabeling cost
becomes $O(\varepsilon^{-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 $\Theta(\varepsilon^{-1}\log^{3/2} n)$.

Data Structures and Algorithms