A note on the depth of optimal fanout-bounded prefix circuits
I. S. Sergeev · 2025
Read A note on the depth of optimal fanout-bounded prefix circuits by I. S. Sergeev (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-23657.txt.
Description
Igor Sergeev settles the depth question for a special family of arithmetic circuits that compute prefix operations. In these, each output combines all inputs up to its position. Optimal prefix circuits use the fewest possible operations, but their outputs can only be fanned out to a limited number of successors when fanout is capped, which forces extra depth.
Sergeev proves that, for fanout bounded by a constant k, the minimal depth of an optimal prefix circuit on N inputs grows like the logarithm of N. That growth uses a base set by a specific polynomial's unique positive root, up to an additive constant. The formula was previously known only for the extreme cases of fanout two and unlimited fanout. His short note, published in English and Russian versions, fills in every intermediate case.
Catalog record
| CREATOR | I. S. Sergeev |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 9 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-23657