On the Complexity of Fanout-Bounded ParallelPrefix Circuits

We prove that the complexity of a universal depth- n parallel prefix circuit on 2ⁿ inputs with fanout bounded by $$ 2 $$ is at least 0.75(n-1)2ⁿ . We also propose a number of simple constructions and upper complexity bounds on fanout- $$ 2 $$ prefix circuits of depth $$ n+k $$ .