Simulating (log c n )-wise independence in NC

Abstract

A general framework for removing randomness from randomized NC algorithms whose analysls uses only pol ylogarlthmic 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 y problem. which can be used to obtain many other NC algorithms, mcludmg a better NC edge coloring algorithm. As another application of the techniques in this paper. an NC algorlthm for the h ypergraph coloring problem M provided.