Skip to content

Author

A. Krapivin

3 papers indexed here

We haven’t gathered this author’s papers yet. Follow them and we’ll fetch their work.

Not the right person? Other researchers publish under this name.

Preprint Nov 2026

Incremental Open Addressing Has No Time-Space Tradeoff

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
Preprint Nov 2026

The CNF Encoding Complexity of Boolean Functions

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
Preprint Oct 2026

Optimal Worst-Case Open Addressing: Braided Cuckoo Hashing

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.