Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits
Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi · Society for Industrial and Applied Mathematics eBooks · 2024
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.