patternMinor
Why is tabulated hashing 3-wise independent but not 4-wise independent?
Viewed 0 times
whytabulatedindependentbutwisehashingnot
Problem
Tabulated hashing uses tables of random numbers to compute hash values.
Suppose $|\mathcal{U}| = 2^w \times 2^w$ and $m = 2^l$, so that the items being hashed are pairs $(x,y)$ where $x$ and $y$ are $w$-bit strings (or $2w$-bit strings broken in half), and hash values are
$l$-bit strings.
Let $A[0 \cdots 2^w-1]$ and $B[0 \cdots 2^w-1]$ be arrays of $l$-bit strings. $A$ and $B$ can be though of as $2^w \times l$ dimensional array of bits.
Define the hash function $h_{A, B} : \mathcal{U} \to [m]$ by setting $h_{A, B}(x, y) = A[x] \oplus B[y]$, where $\oplus$ denotes bit-wise exclusive-or.
Let $\mathcal{H}'$ denote the set of all possible functions $h_{A, B}$.
Can someone explain why is $\mathcal{H}'$ 3-wise independent and not 4-wise independent?
Suppose $|\mathcal{U}| = 2^w \times 2^w$ and $m = 2^l$, so that the items being hashed are pairs $(x,y)$ where $x$ and $y$ are $w$-bit strings (or $2w$-bit strings broken in half), and hash values are
$l$-bit strings.
Let $A[0 \cdots 2^w-1]$ and $B[0 \cdots 2^w-1]$ be arrays of $l$-bit strings. $A$ and $B$ can be though of as $2^w \times l$ dimensional array of bits.
Define the hash function $h_{A, B} : \mathcal{U} \to [m]$ by setting $h_{A, B}(x, y) = A[x] \oplus B[y]$, where $\oplus$ denotes bit-wise exclusive-or.
Let $\mathcal{H}'$ denote the set of all possible functions $h_{A, B}$.
Can someone explain why is $\mathcal{H}'$ 3-wise independent and not 4-wise independent?
Solution
For any $h = h_{A,B}$ and $x,x',y,y' \in \{0,1\}^w$,
$$
h(x,y) \oplus h(x',y) \oplus h(x,y') \oplus h(x',y') = 0.
$$
$$
h(x,y) \oplus h(x',y) \oplus h(x,y') \oplus h(x',y') = 0.
$$
Context
StackExchange Computer Science Q#136649, answer score: 3
Revisions (0)
No revisions yet.