Let $V=\{0,1\}^m$ and $H\subseteq V\to V$ a 2-universal family of hash functions. Fix two sets $A,B\subseteq V$. Call a hash function $h\in H$ $\varepsilon$-good for $A,B$ if: $$ |\Pr_{x\in V} [x\in A \cap h(x)\in B]-\rho(A)\rho(B)|\leq \varepsilon $$ where $\rho(C) = \frac{|C|}{|V|}$. Prove that for any $A,B\subseteq V, \varepsilon>0$, $$ \Pr_{h\in H} [h \space is \space not \space \varepsilon-good \space for \space A,B] \leq \frac{\rho(A)\rho(B)(1-\rho(B))}{\varepsilon^2 |V|} \leq \frac{1}{\varepsilon^2 |V|}$$ Any suggestions?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.