Deterministic factorization of constant-depth algebraic circuits in subexponential time
Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf · 2025
Read Deterministic factorization of constant-depth algebraic circuits in subexponential time by Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf (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-2504-08063.txt.
Description
Somnath Bhattacharjee and four co-authors found a deterministic algorithm in twenty twenty-five. It was long sought. It factors polynomials given as constant-depth algebraic circuits. Randomized factorization has been around for decades. Deterministic forms held out against all tries, even for sparse polynomials. Their algorithm runs in subexponential time. It gives back circuits for each irreducible factor, with its multiplicity.
The proof leans on fine points in the power series roots of constant-depth circuits. A key step is about a known pseudorandom generator. In past work it kept non-zeroness. Here it is shown to keep irreducibility too. That is true of a circuit and of its factors. As a corollary, sparse polynomials get a first subexponential deterministic factorization. The result chips at a core derandomization problem in algebraic complexity theory.
Catalog record
| CREATOR | Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 162 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-08063