{"ID":2824453,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.23657","arxiv_id":"2512.23657","title":"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_{α_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$.","short_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_{α_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=...","url_abs":"https://arxiv.org/abs/2512.23657","url_pdf":"https://arxiv.org/pdf/2512.23657v1","authors":"[\"Igor S. Sergeev\"]","published":"2025-12-29T18:11:09Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}