English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

This paper considers the basic question of how strong of a probabilisticguarantee can a hash table, storing $n$ $(1 + \Theta(1)) \log n$-bit key/valuepairs, offer? Past work on this question has been bottlenecked by limitationsof the known families of hash functions: The only hash tables to achievefailure probabilities less than $1 / 2^{\polylog n}$ require access tofully-random hash functions -- if the same hash tables are implemented usingthe known explicit families of hash functions, their failure probabilitiesbecome $1 / \poly(n)$.  To get around these obstacles, we show how to construct a randomized datastructure that has the same guarantees as a hash table, but that \emph{avoidsthe direct use of hash functions}. Building on this, we are able to construct ahash table using $O(n)$ random bits that achieves failure probability $1 /n^{n^{1 - \epsilon}}$ for an arbitrary positive constant $\epsilon$.  In fact, we show that this guarantee can even be achieved by a \emph{succinctdictionary}, that is, by a dictionary that uses space within a $1 + o(1)$factor of the information-theoretic optimum.  Finally we also construct a succinct hash table whose probabilisticguarantees fall on a different extreme, offering a failure probability of $1 /\poly(n)$ while using only $\tilde{O}(\log n)$ random bits. This latter resultmatches (up to low-order terms) a guarantee previously achieved byDietzfelbinger et al., but with increased space efficiency and with severalsurprising technical components.

A Hash Table Without Hash Functions, and How to Get the Most Out of Your Random Bits