On the Complexity of Fanout-Bounded ParallelPrefix Circuits

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