However, we stress that for each level \(i\) , we require the random generator to be fully independent from the random generators at previous levels \(1,\ldots ,i-1\) .
It is well known [1]} that a pairwise independent random number generator can be implemented using \(\Theta (\log {n})\)  random bits
so that it generates numbers in constant time in the word RAM model. As a result, if \(\Theta (\ell \log {n})\)  random bits are provided, each \(H_i^0\)  can be constructed in \(O(si)=O(mpi)\)  time and has \(O(mpi)\)  edges.
