It is shown that complexity of implementation of prefix sums of m variables (i.e. functions x1xi, 1im) by circuits of depth log2m in the case m=2n is exactly 352n?(85+35(nmod2))2n2+n+5 As a consequence, for an arbitrary m an upper bound (35?o(1))m holds. In addition, an upper bound 3311?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
展开▼
机译：结果表明，在m = 2n的情况下，深度为log2m的电路实现m个变量（即函数x1xi，1im）的前缀和的复杂度正好是352n？（85 + 35（nmod2））2n2 + n + 5结果，对于任意的m，上限（35？o（1））m成立。另外，获得了最小深度前缀电路相对于XOR运算的复杂度的上限3311Δo（1）m。还建立了在电路深度不同限制下的一些新界限
展开▼
