We show how to implement a dynamic array $A[1, n]$ with symbols from a fixed alphabet $\Sigma$, while supporting $O(1)$-time queries and updates, and using a total space of $$ \log \binom{|\Sigma|}{m} + \left(1 + O\left(\frac{\log \log n}{\log n}\right)\right) \cdot \left(\sum_{\sigma \in \Sigma} f_\sigma \log (n / f_\...
G. Blelloch, Yang Hu, William Kuszmaul et al.· 2 citations
This paper considers the following basic question: If an (ordered) linear-probing hash table is allowed \emph{two} hash functions, instead of one, how does this change the expected insertion and query time, as a function of the load factor $1 - \epsilon$? We prove that the \emph{greedy two-choice insertion strategy} ac...
Amir Azarmehr, Michael A. Bender, William Kuszmaul et al.· 0 citations
A dynamic dictionary is constructed that supports operations in $O(\log\varepsilon^{-1}/\log\log\varepsilon^{-1})$ expected amortized time and uses bits of space, and proves a matching lower bound, showing that the time-space tradeoff is optimal even in the \emph{static} case.
G. Blelloch, Yang Hu, William Kuszmaul et al.· 1 citation
This paper considers the following basic question: Does request fragmentation fundamentally change the problem of memory allocation, and if so, how, and finds that even using $k = 1 + o(1)$ request fragmentation, the optimal competitive ratiocollapses to $\Theta(\log M)$.
Michael A. Bender, A. Conway, Martín Farach-Colton et al.· 1 citation
It is shown that, for sufficiently large $p, the expected maximum loads in the modular and real settings are essentially the same, giving an alternative route to an $n^{1/3+o(1)}$ upper bound, and the Kakeya conjecture for upper Minkowski dimension is proved.
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.
