Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits

For 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 [For15] and on subexponential time deterministic PIT algorithms for constant depth algebraic circuits from the recent work of Limaye, Srinivasan and Tavenas [LST21].