Deterministic Polynomial-time Exact-root Computation for Sparse Polynomials with Bounded Total Degree

We study the problem of deterministically computing the exact root of a sparse polynomial in the multivariate setting. Let f ∈ F[x1,ldots,xn] be a nonzero polynomial that is an exact e-th power, say f = ge. Suppose f is s-sparse, has an individual degree of at most d, and a total degree of D = tdeg(f). We prove a sparsity bound on the base polynomial g: [ |g|0 ≤ sD(2d+2)/e + 1. ] Based on this bound, we develop a deterministic algorithm that computes the base g. % In contrast to the general deterministic factorization algorithm of Bhargava, Saraf, and Volkovich citeBhargavaSarafVolkovich2020, which achieves only a quasi-polynomial dependence on the input parameters, our algorithm is polynomial-time in the setting where the total degree D is bounded. Specifically, the overall complexity is [ polyleft(sO(Dd), n, d, Dright) + s· R(e), ] % where R(e) denotes the cost of constructing a single e-th root of a scalar in the base field F, and, when operatornamechar(F)mid e, the cost of computing a single Frobenius root of a scalar. % This term is field-dependent, and over finite fields, mathbbQ, or number fields with a suitable representation, it is absorbed into the polynomial complexity bound. % Within the bounded total-degree regime, this yields a deterministic polynomial-time algorithm for exact-root computation.