THE PROBABILISTIC METHOD YIELDS DETERMINISTIC PARALLEL ALGORITHMS

We present a technique for converting RNC algorithms into NC algorithm s. Our approach is based on a parallel implementation of the method of conditional probabilities. This method was used to convert probabilis tic proofs of existence of combinatorial structures into polynomial ti me deterministic algorithms. It has the apparent drawback of being ext remely sequential in nature. We show certain general conditions under which it is possible to use this technique for devising deterministic parallel algorithms. We use our technique to devise an NC algorithm fo r the set balancing problem. This problem turns out to be a useful too l for parallel algorithms. Using our de-randomization method and the s et balancing algorithm, we provide an NC algorithm for the lattice app roximation problem. We also use the lattice approximation problem to b ootstrap the set balancing algorithm, and the result is a more process or efficient algorithm. The set balancing algorithm also yields an NC algorithm for near-optimal edge coloring of simple graphs. Our methods also extend to the parallelization of various algorithms in computati onal geometry that rely upon the random sampling technique of Clarkson . Finally, our methods apply to constructing certain combinatorial str uctures, e.g., Ramsey graphs and independent sets and covers of hyperg raphs. (C) 1994 Academic Press, Inc.