Exercises 22. 4. 2021: Hash functions

\( \def\H{\mathcal{H}} \def\U{\mathcal{U}} \def\B{\mathcal{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