A dictionary data structure maintains a set of at most n keys from the universe U under key
insertions and deletions, such that given a query x∈U, it returns if x is in the set. Some …

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 …

Augmented B-trees (aB-trees) are a broad class of data structures. The seminal work
“succincter” by Pǎtraşcu 1 showed that any aB-tree can be stored using only two bits of …

Dictionaries have been one of the central questions in data structures. A dictionary data
structure maintains a set of key-value pairs under insertions and deletions such that given a …

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 …