Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits

We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial f computed by a constant-depth circuit over rational numbers, and outputs a list L of circuits (of unbounded depth and possibly with division gates) that contains all irreducible factors of f computable by constant-depth circuits. This list L might also include circuits that are spurious: they either do not correspond to factors of f or are not even well-defined, e.g. the input to a division gate is a sub-circuit that computes the identically zero polynomial. The key technical ingredient of our algorithm is a notion of the pseudo-resultant of f and a factor g , which serves as a proxy for the resultant of g and f / g , with the advantage that the circuit complexity of the pseudo-resultant is comparable to that of the circuit complexity of f and g . This notion, which might be of independent interest, together with the recent results of Limaye, Srinivasan and Tavenas 19 helps us derandomize one key step of multivariate polynomial factorization algorithms — that of deterministically finding a good starting point for Newton Iteration for the case when the input polynomial as well as the irreducible factor of interest have small constant-depth circuits.