We now show that the basis of our construction, i.e., pairwise independent sampling at \(O(\log {n})\)  levels, yields an interesting low-randomness alternative to Karger's result [1]} saying that if a graph \(G\)  is \(c^{\prime }\) -edge-connected graph,
where \(c^{\prime }=\Omega ((c+\log {n})/p)\) ,
then \(G(p)\)  is \(c\) -edge-connected with high probability (depending on the constant hidden in the \(\Omega \)  notation).
Roughly speaking, Karger's proof
applies a Chernoff bound to an exponential number of cuts in \(G\)  and therefore requires sampling with full independence, i.e., \(\Theta (m)\)  random bits.
We show that the graph \(H_0^\ell \)  has a similar property, but requires only polylogarithmic number of random bits: pairwise independence requires \(O(\log {n})\)  bits, and there are \(O(\log {n})\)  sampling levels.
