Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2506.23214 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909665550401536 |
|---|---|
| author | Bhattacharjee, Somnath Kumar, Mrinal Rai, Shanthanu S. Ramanathan, Varun Saptharishi, Ramprasad Saraf, Shubhangi |
| author_facet | Bhattacharjee, Somnath Kumar, Mrinal Rai, Shanthanu S. Ramanathan, Varun Saptharishi, Ramprasad Saraf, Shubhangi |
| contents | We show that algebraic formulas and constant-depth circuits are closed under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas respectively.
Our result turns out to be an elementary consequence of a fundamental and surprising result of Furstenberg from the 1960s, which gives a non-iterative description of the power series roots of a bivariate polynomial. Combined with standard structural ideas in algebraic complexity, we observe that this theorem yields the desired closure results.
As applications, we get alternative (and perhaps simpler) proofs of various known results and strengthen the quantitative bounds in some of them. This includes a unified proof of known closure results for algebraic models (circuits, branching programs and VNP), an extension of the analysis of the Kabanets-Impagliazzo hitting set generator to formulas and constant-depth circuits, and a (significantly) simpler proof of correctness as well as stronger guarantees on the output in the subexponential time deterministic algorithm for factorization of constant-depth circuits from a recent work of Bhattacharjee, Kumar, Ramanathan, Saptharishi & Saraf. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_23214 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Closure under factorization from a result of Furstenberg Bhattacharjee, Somnath Kumar, Mrinal Rai, Shanthanu S. Ramanathan, Varun Saptharishi, Ramprasad Saraf, Shubhangi Computational Complexity We show that algebraic formulas and constant-depth circuits are closed under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas respectively. Our result turns out to be an elementary consequence of a fundamental and surprising result of Furstenberg from the 1960s, which gives a non-iterative description of the power series roots of a bivariate polynomial. Combined with standard structural ideas in algebraic complexity, we observe that this theorem yields the desired closure results. As applications, we get alternative (and perhaps simpler) proofs of various known results and strengthen the quantitative bounds in some of them. This includes a unified proof of known closure results for algebraic models (circuits, branching programs and VNP), an extension of the analysis of the Kabanets-Impagliazzo hitting set generator to formulas and constant-depth circuits, and a (significantly) simpler proof of correctness as well as stronger guarantees on the output in the subexponential time deterministic algorithm for factorization of constant-depth circuits from a recent work of Bhattacharjee, Kumar, Ramanathan, Saptharishi & Saraf. |
| title | Closure under factorization from a result of Furstenberg |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2506.23214 |