2026-07-23T17:40:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27062 2026-07-23T11:36:19Z ddc:004 open_access

On Factorization of Sparse Polynomials of Bounded Individual Degree Chuyoon, Aminadav Shpilka, Amir algebraic complexity theory sparse polynomials factorization reconstruction We study sparse polynomials with bounded individual degree and the class of their factors. In particular we obtain the following algorithmic and structural results: 1) A deterministic polynomial-time algorithm for finding all the sparse divisors of a sparse polynomial with bounded individual degree. As part of this, we establish the first upper bound on the number of non-monomial irreducible factors of such polynomials. 2) A poly(n,s^{dlog 𝓁})-time algorithm for recovering 𝓁 irreducible s-sparse polynomials of bounded individual degree d from blackbox access to their product (which is not necessarily sparse). This partially resolves a question posed in [Pranjal Dutta et al., 2024]. In particular, when 𝓁 = O(1), the algorithm runs in polynomial time. 3) Deterministic algorithms for factoring a product of s-sparse polynomials of bounded individual degree d from blackbox access. Over fields of characteristic zero or sufficiently large, the algorithm runs in poly(n,s^{d³log n})-time; over arbitrary fields it runs in poly(n,{(d²)!},s^{d⁵log n})-time. This improves upon the algorithm of [Bhargava et al., 2020], which runs in poly(n,s^{d⁷log n})-time and applies only to a single sparse polynomial of bounded individual degree. In the case where the input is a single sparse polynomial, we give an algorithm that runs in poly(n,s^{d²log n})-time. 4) Given blackbox access to a product of (not necessarily sparse or irreducible) factors of sparse polynomials of bounded individual degree, we give a deterministic polynomial-time algorithm for finding all irreducible sparse multiquadratic factors of it (along with their multiplicities). This generalizes the algorithms of [Volkovich, 2015] and [Volkovich, 2017]. We also show how to decide whether such a product is a complete power (in case it is defined over a field of zero or large enough characteristic), extending the algorithm of [Bisht and Volkovich, 2025]. Our algorithms most naturally apply over fields of zero or sufficiently large characteristic. To handle arbitrary fields, we introduce the notion of primitive divisors for a class of polynomials, which may be of independent interest. This notion enables us to adapt ideas of [Bisht and Volkovich, 2025] and remove characteristic assumptions from most of our algorithms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aminadav Chuyoon and Amir Shpilka 2026 Is Part Of LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2026.20 urn:nbn:de:0030-drops-270627 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.20 eng https://creativecommons.org/licenses/by/4.0/legalcode