A data structure is said to be strongly history independent if its state is fully determined by its
current set of elements (and random bits). One of the most basic questions that strongly …

A growing line of work shows how learned predictions can be used to break through worst-
case barriers to improve the running time of an algorithm. However, incorporating …

A data structure is history independent if its internal representation reveals nothing about the
history of operations beyond what can be determined from the current contents of the data …

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=(1+\Theta (1)) n $. The goal is to …

A data structure is called history independent if its internal memory representation does not
reveal the history of operations applied to it, only its current state. In this paper we study …

This thesis revisits some of the oldest and most basic questions in the theory of randomized
data structures—questions such as: How efficient is a linear probing hash table? How fast …

In the Online List Labeling problem, a set of $ n\leq N $ elements from a totally ordered
universe must be stored in sorted order in an array with $ m= N+\lceil\varepsilon N\rceil …

In the online sorting problem, $ n $ items are revealed one by one and have to be placed
(immediately and irrevocably) into empty cells of a size-$ n $ array. The goal is to minimize …