ECCC-Report TR13-041https://eccc.weizmann.ac.il/report/2013/041Comments and Revisions published for TR13-041en-usSun, 24 Mar 2013 07:45:41 +0200
Paper TR13-041
| On the complexity of parallel prefix circuits |
Igor Sergeev
https://eccc.weizmann.ac.il/report/2013/041It is shown that complexity of implementation of prefix sums of $m$ variables (i.e. functions $x_1 \cdot \ldots\cdot x_i$, $1\le i \le m$) by circuits of depth $\lceil \log_2 m \rceil$ in the case $m=2^n$ is exactly $$3.5\cdot2^n - (8.5+3.5(n \bmod 2))2^{\lfloor n/2\rfloor} + n + 5.$$ As a consequence, for an arbitrary $m$ an upper bound $(3.5-o(1))m$ holds. In addition, an upper bound $\left(3\frac{3}{11}-o(1)\right)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.
Sun, 24 Mar 2013 07:45:41 +0200https://eccc.weizmann.ac.il/report/2013/041