Preprint
Aug 2026
Optimal Time-Space Tradeoff for Dynamic Difference-Encoded Dictionaries
The dynamic dictionary is a fundamental data structure that maintains a set $S\subset [U]$ of size $n$ (we assume $n=U^{1-\Theta(1)}$), supporting insertions, deletions and membership queries. Previous works mostly focused on constructing dictionaries that support operations in $O(1)$ time and use space as close to the...
G. Blelloch, Yang Hu, William Kuszmaul et al.
· 1 citation