Set Families with Low Pairwise Intersection

A $left(n,ell,gammaright)$-sharing set family of size $m$ is a family of sets $S_1,ldots,S_msubseteq [n]$ s.t. each set has size $ell$ and each pair of sets shares at most $gamma$ elements. We let $mleft(n,ell,gammaright)$ denote the maximum size of any such set family and we consider the following question: How large can $mleft(n,ell,gammaright)$ be? $left(n,ell,gammaright)$-sharing set families have a rich set of applications including the construction of pseudorandom number generators and usable and secure password management schemes. We analyze the explicit construction of Blocki et al using recent bounds on the value of the $t$th Ramanujan prime. We show that this explicit construction produces a $left(4ell^2ln 4ell,ell,gammaright)$-sharing set family of size $left(2 ell ln 2ellright)^{gamma+1}$ for any $ellgeq gamma$. We also show that the construction of Blocki et al can be used to obtain a weak $left(n,ell,gammaright)$-sharing set family of size $m$ for any $m >0$. These results are competitive with the inexplicit construction of Raz et al for weak $left(n,ell,gammaright)$-sharing families. We show that our explicit construction of weak $left(n,ell,gammaright)$-sharing set families can be used to obtain a parallelizable pseudorandom number generator with a low memory footprint by using the pseudorandom number generator of Nisan and Wigderson. We also prove that $mleft(n,n/c_1,c_2nright)$ must be a constant whenever $c_2 leq frac{2}{c_1^3+c_1^2}$. We show that this bound is nearly tight as $mleft(n,n/c_1,c_2nright)$ grows exponentially fast whenever $c_2 > c_1^{-2}$.