# zbMATH — the first resource for mathematics

Probabilistic parallel prefix computation. (English) Zbl 0772.94019
Summary: Given inputs $$x_ 1,\dots,x_ n$$, which are independent identically distributed random variables over a domain $$D$$, and an associative operation $$\circ$$, the probabilistic prefix computation problem is to compute the product $$x_ 1\circ x_ 2\circ\cdots\circ x_ n$$ and its $$n-1$$ prefixes. Instances of this problem are finite state transductions on random inputs, the addition or subtraction of two random $$n$$-bit binary numbers, and the multiplication or division of a random $$n$$-bit binary number by a constant.
The best known constant fan-in circuits for these arithmetic operations had logarithmic depth, linear size, and produce no errors. Furthermore, matching lower bounds for depth and size (up to constant factors between the upper and lower bounds) had previously been obtained for the case of constant fan-in circuits with no errors.
We give arithmetic circuits for probabilistic prefix computation, which 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>0$$. For any constant, fan-in circuits computing these random arithmetic operations with error probability $$n^{- \alpha}$$, we prove the circuit depth must be bounded from below by $$\Omega(\log\log n)$$. Hence, we conclude our circuits have asymptotically optimal depth among circuits with error probability $$n^{-\alpha}$$.
We also give 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.

##### MSC:
 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010) 94B70 Error probability in coding theory
Full Text: