However, our new randomized \(c\) -certificate that is the key to obtaining the new reduction requires only pairwise independent sampling to work. This is in sharp contrast with the certificate of Karger [1]}, used in the construction of Thorup's data structure (Theorem REF ), which requires full independence, i.e., \(\Theta (m)\)  random bits. We show that we may instead plug our new certificate into Thorup's data structure at the cost of a single additional logarithmic factor in the running time. Since Karger's certificate constitutes the only use of randomness in Thorup's data structure, and full independence in our construction is required only for invoking Theorem REF , we obtain the below low-randomness version of our main result.
