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
The classical memory-allocation problem captures the task of placing objects of different sizes in memory, while minimizing the so-called memory high-water mark. It has been known since the early 1970s that the optimal competitive ratio for any deterministic online allocator is $\Theta(\log M)$, where $M$ is the volume...
Michael A. Bender, A. Conway, Martín Farach-Colton et al.· 1 citation
Affine modular linear hashing is one of the simplest classical hash families. For a prime $p>u$, the hash function is obtained by choosing $s,t$ uniformly from $\mathbb{Z}_p$ and mapping each key $x \in \{0,\ldots,u-1\}$ to one of $n$ bins by $h(x) = [(sx+t) \bmod p] \bmod n$. Despite its simplicity, the maximum load o...
Ainesh Bakshi, A. Conway, Hanna Komlós et al.· 1 citation
First proposed in 1968, quadratic probing has stood for more than half a century as one of the simplest and most widely used hash-table designs in computer science. It is conjectured that, at load factor $1 - \epsilon$, the hash table achieves $O(\epsilon^{-1})$ expected insertion time. But even proving a bound of the...
Yang Hu, William Kuszmaul, Jingxun Liang et al.· 0 citations
This thesis surveys major algorithmic developments for computing treewidth and discusses the compression and improvement paradigm developed in the 1990s, especially in the work of Bodlaender and Kloks, and Bodlaender and Hagerup.
Taek-Yoon Kim, Chair Guy Blelloch, William Kuszmaul· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
