ECCC-Report TR24-043https://eccc.weizmann.ac.il/report/2024/043Comments and Revisions published for TR24-043en-usWed, 06 Mar 2024 09:49:24 +0200
Paper TR24-043
| Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits |
Varun Ramanathan,
Mrinal Kumar,
Ramprasad Saptharishi,
Ben Lee Volk
https://eccc.weizmann.ac.il/report/2024/043We 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.
Wed, 06 Mar 2024 09:49:24 +0200https://eccc.weizmann.ac.il/report/2024/043