Marius Zimand

Online matching games in bipartite expanders: applications to bitprobes and dictionaries with non-adaptive probing

A dictionary is a data structure which stores pairs (key, value). The operation query on input key returns value if the dictionary contains a pair (key, value) and nil otherwise. A dynamic dictionary also supports the insert and delete operations. The model with cells of bitsize $n + m + 1$ is used, where $n$ and $m$ a...