On the Complexity of Fanout-Bounded Parallel Prefix 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 complexitybounds on fanout- \(2\) prefix circuits of depth \(n+k\) .