The hash function h maps binary vectors of dimension m to binary vectors of dimension n, where m > n, with the help of an n×m matrix H with binary elements that are generated randomly.
computer science
Description
Q1. (25 points - part (a) and (b) are purely written questions, part (c) requires implementation and code submission) In this question, you will analyze the empirical and theoretical collision probability for a new hash function.
The hash function h maps binary vectors of dimension m to binary vectors of dimension n, where m > n, with the help
of an n×m matrix H with binary elements that are generated randomly. More specifically, given the matrix H, the hash
function h : {0,1}
m → {0,1}
n provides the following hash value for a key x ∈ {0,1}
m :
where the mod operator is applied element-wise (to the obtained vector Hx).
For instance, if m = 3, n = 2, H is the matrix consisting of all ones, x is the vector of all ones, then the obtained vector
Hx will be the vector of all threes, and when the element-wise mod 2 is applied, the two-dimensional vector h(x) will be
obtained as the vector of all ones.
