In this paper, we show that there is no time-space tradeoff in incremental open addressing: there is an incremental open-addressed hash table that supports $O(1)$ worst-case expected time insertions, positive queries, and negative queries, at any load factor (even load factor $1$). As an intermediate result, we also re...
Martín Farach-Colton, A. Krapivin, William Kuszmaul· 0 citations
We study the minimum number of clauses required to encode a boolean function into a CNF formula with auxiliary variables. Our main result is that if a boolean function can be evaluated in nondeterministic time $t$ (in the RAM model) with $m$ bits of advice such that at most $b$ bits of advice are accessed for each inpu...
A. Krapivin, Benjamin Przybocki, B. Subercaseaux· 0 citations
In this paper, we introduce braided cuckoo hashing, an open-addressed hash table that supports load factor up to $1 - \varepsilon$ (for some parameter $\varepsilon \in (0, 1)$), while supporting queries, insertions, and deletions in worst-case time $O(\log \varepsilon^{-1})$, with high probability. This result represen...
A. Krapivin, 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.