Bonnie Berger


Simulating (logc n)-Wise Independence in NC

Bonnie Berger and John Rompel


A general framework for removing randomness from randomized NC algorithms whose analysis uses only polylogarithmic independence is developed. Previously, no techniques were known to remove the randomness from those randomized NC algorithms depending on more than constant independence. One application of our techniques is an NC algorithm for the set discrepancy problem which can be used to obtain many other NC algorithms, including a better NC edge coloring algorithm. As another application of the techniques in this paper, an NC algorithm for the hypergraph coloring problem is provided.