Score: 0

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

Published: December 29, 2025 | arXiv ID: 2512.23657v1

By: Igor S. Sergeev

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_{α_k} N \pm O(1)}$, where $α_k$ is the unique positive root of the polynomial ${2+x+ x^2+\ldots + x^{k-2}-x^k}$. This bound was previously known in the cases $k=2$ and $k=\infty$.

Category
Computer Science:
Data Structures and Algorithms