|
|
|
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.
|
|
|
|
|
|