We show that the GCD of two univariate polynomials can be computed by (piece-wise) algebraic circuits of constant depth and polynomial size over any sufficiently large field, regardless of the characteristic. This extends a recent result of Andrews & Wigderson who showed such an upper bound over fields of zero or large characteristic. Our proofs are based on a recent work of Bhattacharjee, Kumar, Rai, Ramanathan, Saptharishi \& Saraf that shows closure of constant depth algebraic circuits under factorization. On our way to the proof, we show that any $n$-variate symmetric polynomial $P$ that has a small constant depth algebraic circuit can be written as the composition of a small constant depth algebraic circuit with elementary symmetric polynomials. This statement is a constant depth version of a result of Bläser & Jindal, who showed this for algebraic circuits of unbounded depth. As an application of our techniques, we also strengthen the closure results for factors of constant-depth circuits in the work of Bhattacharjee et al. over fields for small characteristic.

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.

While efficient randomized algorithms for factorization of polynomials given by algebraic circuits have been known for decades, obtaining an even slightly non-trivial deterministic algorithm for this problem has remained an open question of great interest. This is true even when the input algebraic circuit has additional structure, for instance, when it is a constant-depth circuit. Indeed, no efficient deterministic algorithms are known even for the seemingly easier problem of factoring sparse polynomials or even the problem of testing the irreducibility of sparse polynomials.In this work, we make progress on these questions: we design a deterministic algorithm that runs in subexponential time, and when given as input a constant-depth algebraic circuit C over the field of rational numbers, it outputs algebraic circuits (of potentially unbounded depth) for all the irreducible factors of C, together with their multiplicities. In particular, we give the first subexponential time deterministic algorithm for factoring sparse polynomials.For our proofs, we rely on a finer understanding of the structure of power series roots of constant-depth circuits and the analysis of the Kabanets-Impagliazzo generator. In particular, we show that the Kabanets-Impagliazzo generator constructed using low-degree hard polynomials (explicitly constructed in the work of Limaye, Srinivasan & Tavenas) preserves not only the non-zeroness of small constant-depth circuits (as shown by Chou, Kumar & Solomon), but also their irreducibility and the irreducibility of their factors.

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.