A note on the depth of optimal fanout-bounded prefix circuits

Abstract

It is shown that the minimal depth of an optimal prefix circuit (i.e., a zero-deficiency circuit) on $N$ inputs with fanout bounded by $k$ is ${\log }_{{\alpha }_k}N\pm O(1)$, where ${\alpha }_k$ is the unique positive root of the polynomial $2+x+x^2+\dots +x^{k-2}-x^k$. This bound was previously known in the cases $k=2$ and $k=\infty$.

5 pages (in English); 5 pages (in Russian)