A note on the depth of optimal fanout-bounded prefix circuits
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911343940993024 |
|---|---|
| author | Sergeev, Igor S. |
| author_facet | Sergeev, Igor S. |
| contents | 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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_23657 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A note on the depth of optimal fanout-bounded prefix circuits Sergeev, Igor S. Data Structures and Algorithms 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$. |
| title | A note on the depth of optimal fanout-bounded prefix circuits |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2512.23657 |