Exercises 22. 4. 2021: Hash functions

$$\def\H{\mathcal{H}} \def\U{\mathcal{U}} \def\B{\mathcal{B}}$$

Notation:

• $$\U$$ : universe
• $$U = |\U|$$
• $$\B$$ : buckets
• $$m = |\B|$$

Ex. 1: Universality and independence

1. Recall the definition of c-universality and (k,c)-independence.
2. Consider a family $$\mathcal{H}_1 = \{h(x) = x\}$$ that contains a single hash function $$h(x) = x$$ (that is, $$\B = \U$$. Is family $$\H_1$$ c-universal for some c? Is it (k,c)-independent for some k and c?
3. Show that family $$\H_2 = \{h_a(x) = a | a\in\B\}$$ of all constant functions is (1,1)-independent. Also show $$\H_2$$ is not (2,c)-independent nor c-universal for any c.
4. Prove the following claim from the lecture
• $$\H$$ is (k,c)-independent $$\Rightarrow$$ $$\H$$ is (k-1,c)-independent ($$k > 1$$)
• $$\H$$ is (2,c)-independent $$\Rightarrow$$ $$\H$$ is c-universal