Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
<|reference_start|>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, 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.<|reference_end|>
@article{kumar2024towards,
    title={Towards Deterministic Algorithms for Constant-Depth Factors of
  Constant-Depth Circuits},
    author={Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk},
    journal={arXiv preprint arXiv:2403.01965},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.01965},
    primaryClass={cs.CC cs.DS}
}