We denote by $[t]$ the set $\{1,2,\ldots,t\}$.

A $(n,k)$-perfect hashing family is a set of functions $H=\{h_i:[n]\to[k]\}$ such that for every set $S\subset [n], |S|\leq k$, there exists some $h_S \in H$ such that $h_S$ is injective on $S$.

There are known (deterministic) builds of such family of size $O(e^{k+log^2k}log n)$, while there is a $\Omega(e^k \cdot \frac{log n}{\sqrt k})$ lower bound , which is almost tight.

We define an extension of such families as follows:

A family of functions $\mathcal F=\{f_i:[n]\to [k]\}$ is a $(n,r,k)$-perfect hashing family if for every set of sets, $\mathcal S=\{S_1,S_2,\ldots,S_r\subseteq [n]\}$, such that $$|\mathcal S|=r,\ \forall i:|S_i|=k,\ \forall j\neq i:S_i\cap S_j = \emptyset$$

There exists a function $f\in \mathcal F$ which is injective on all $S_i\in \mathcal S$.

That is, every set of $r$ disjoint sets of indices of size $k$ there exists a single function which is injective on all of them.

What is the smallest $(n,r,k)$-perfect hashing family we can build?

Specifially, I'm mainly interested in the $r=2$ case, but this might be useful to others for general $r$ values.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.