ECCC-Report TR23-139https://eccc.weizmann.ac.il/report/2023/139Comments and Revisions published for TR23-139en-usMon, 18 Sep 2023 15:22:53 +0300
Paper TR23-139
| Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits |
Varun Ramanathan,
Mrinal Kumar,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2023/139For every constant $d$, we design a subexponential time deterministic algorithm that takes as input a multivariate polynomial $f$ given as a constant depth algebraic circuit over the field of rational numbers, and outputs all irreducible factors of $f$ of degree at most $d$ together with their respective multiplicities. Moreover, if $f$ is a sparse polynomial, then the algorithm runs in quasipolynomial time.
Our results are based on a more fine-grained connection between polynomial identity testing (PIT) and polynomial factorization in the context of constant degree factors and rely on a clean connection between divisibility testing of polynomials and PIT due to Forbes and on subexponential time deterministic PIT algorithms for constant depth algebraic circuits from the recent work of Limaye, Srinivasan and Tavenas.Mon, 18 Sep 2023 15:22:53 +0300https://eccc.weizmann.ac.il/report/2023/139