Deterministic factorization algorithm for constant depth algebraic circuits
Deterministic factorization of constant depth circuits from whitebox PIT
Computational Complexity
Summary
Factoring complex math expressions written as constant depth circuits is often challenging, especially when you want a step-by-step, predictable method. The authors found a way to break down such expressions into simpler factors using an existing test that tells if these expressions equal zero, called PIT. Their method works over rational numbers and runs efficiently, making repeated calls to this test. Along the way, they introduce a tool that helps find dependencies in matrices made from these circuits, which may be useful beyond this work.
What this means in practice
- •For computer algebra system developers: Integrate a deterministic factorization method for constant depth circuits using PIT oracles to enhance symbolic computation reliability and performance.
- •For complexity theory tool builders: Use the deterministic kernel-finding algorithm for matrices with constant depth circuit entries to simplify algebraic complexity problems efficiently.
Authors
Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf
Abstract
We show that over the field of rational numbers, there is a deterministic algorithm for factorization of constant depth circuits that makes calls to a (whitebox or blackbox) PIT algorithm for such circuits. The time complexity of the algorithm (and hence the number of calls to the PIT oracle) is polynomially bounded in the size and degree of the input circuit. Our reduction to PIT is fairly simple and general and applies as it is to other natural classes of algebraic circuits like formulas and algebraic branching programs. Prior to this work, the known deterministic factorization algorithms for constant depth circuits crucially relied on \emph{blackbox} PIT [Bhattacharjee et al.]. Our main technical ingredient is an efficient, deterministic algorithm that, when given access to sufficiently high degree truncations of \emph{all} the power series roots of a constant depth circuit, uses oracle calls to any (whitebox or blackbox) PIT algorithm for these circuits, and partitions the roots into the sets of conjugates; thereby identifying the irreducible factors. For our proof, we rely on a root recombination criterion using logarithmic derivatives [Sasaki et al., Bostan et al., Lecerf] and show that this criterion can be efficiently and deterministically implemented for power series roots of constant depth circuits using access to any PIT oracle. On the way, we discuss an algorithm that may be of independent interest: it takes as input a matrix whose entries are multivariate constant depth circuits over a field $\mathbb{F}$, requires oracle access to any PIT algorithm for these circuits and outputs a basis for the $\mathbb{F}$-kernel of this matrix in polynomial time.