בניין מדעי המחשב

 Peeling Close to the Orientability Threshold – Spatial

By Stefan Walzer from University of Cologne, Germany


Abstract:

In cuckoo hash tables each \emph{key} $x$ in a set $S$ of $m$ keys is associated with a random set $e(x) [n]$ of \emph{buckets} by hash functions. Each key must be placed into one of its associated buckets, but each bucket can only hold one key. A successful placement of all keys is called an \emph{orientation}. Sometimes an orientation can be found greedily using \emph{peeling}, meaning we repeatedly look for a bucket that only one unplaced key is associated with and placing thatkey in that bucket.
Many constructions exhibit sharp thresholds with respect to orientability and peelability, i.e. as the load factor $c = \frac{m}{n}$ grows past a critical value, the probability of these properties drops from almost $1$ to almost $0$. In the standard case where for each key $x$ the set $e(x) [n]$ of associated buckets is a \emph{fully random}set of size $k$, the threshold $c_{k}^*$ for orientability significantly exceeds the threshold for peelability. This talk presents for every $k ≥ 3$ and every $z > 0$ a different distribution on sets of size $k$ such
that if the sets $e(x)$ are chosen independently from that distribution, both the peelability and the orientability threshold approach $c_{k}^*$ as $z → ∞$. In particular the reach of the greedy placement algorithm is extended to load factors arbitrarily close to $1$.
Our construction is simple: The $n$ vertices are linearly ordered and each hyperedge selects its $k$ elements uniformly at random from a random range of $\frac{n}{z+1}$ consecutive vertices. We thus exploit the phenomenon of \emph{threshold saturation} via \emph{spatial coupling} discovered in the context of low-density parity-check codes.
Once the connection to data structures is in plain sight, a framework by Kudekar, Richardson and Urbanke (2015) does the heavy lifting in our proof.

 

The lecture will be given in zoom

zoom link:  https://us02web.zoom.us/j/83383478356