On the complexity of parallel prefix circuits.
Igor' Sergeevich Sergeev · Electronic colloquium on computational complexity · 2013
It is shown that complexity of implementation of prefix sums of m variables (i.e. functions x1 ◦ . . . ◦ xi, 1 ≤ i ≤ m) by circuits of depth dlog2 me in the case m = 2n is exactly 3.5 · 2 − (8.5 + 3.5(n mod 2))2bn/2c + n + 5. As a consequence, for an arbitrary m an upper bound (3.5 − o(1))m holds. In addition, an upper bound ( 3 3 11 − o(1) ) m for complexity of the minimal depth prefix circuit with respect to XOR operation is obtained. Some new bounds under different restrictions on the circuit depth are also established.