PROBABILISTIC PARALLEL PREFIX COMPUTATION.
Given inputs x//1 ,. . . ,x//n which are independent, identically distributed, random variables over a domain D, and an associative operation *, the probabilistic prefix computation problem is to compute the product x//1 *x//2 *. . . * x//n and its n-1 prefixes. The author gives circuits for probabilistic prefix computation that for these random arithmetic operations have constant fan-in, linear size, O(log log n) depth, but error probability less than n- alpha for any given alpha less than 0. For any constant fan-in circuits computing these random arithmetic operations with error probability n- alpha , he proves the circuit depth must be lower bounded by OMEGA (log log n). Hence he concludes that these circuits have asymptotically optimal depth among circuits with error probability n- alpha . The author also gives error-free circuits for these random arithmetic operations with constant fan-in at all nodes but one, linear size, and O(log log n) expected delay for their parallel evaluation.
