{"ID":5676819,"CreatedAt":"2026-07-03T03:29:23.032456456Z","UpdatedAt":"2026-07-07T01:06:03.009715918Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.02364","arxiv_id":"2607.02364","title":"Deterministic Polynomial-time Exact-root Computation for Sparse Polynomials with Bounded Total Degree","abstract":"We study the problem of deterministically computing the exact root of a sparse polynomial in the multivariate setting. Let $f \\in \\F[x_1,\\ldots,x_n]$ be a nonzero polynomial that is an exact $e$-th power, say $f = g^e$. 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 \\le s^{D(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 \\cite{BhargavaSarafVolkovich2020}, which achieves only a quasi-polynomial dependence on the input parameters, our algorithm is \\emph{polynomial-time} in the setting where the total degree $D$ is bounded. Specifically, the overall complexity is \\[ \\mathrm{poly}\\left(s^{O(Dd)}, n, d, D\\right) + s\\cdot 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 $\\operatorname{char}(\\F)\\mid e$, the cost of computing a single Frobenius root of a scalar. % This term is field-dependent, and over finite fields, $\\mathbb{Q}$, 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.","short_abstract":"We study the problem of deterministically computing the exact root of a sparse polynomial in the multivariate setting. Let $f \\in \\F[x_1,\\ldots,x_n]$ be a nonzero polynomial that is an exact $e$-th power, say $f = g^e$. Suppose $f$ is $s$-sparse, has an individual degree of at most $d$, and a total degree of $D = \\tdeg...","url_abs":"https://arxiv.org/abs/2607.02364","url_pdf":"https://arxiv.org/pdf/2607.02364v1","authors":"[\"Qiao-Long Huang\",\"Yichuan Cao\",\"Ruichen Qiu\",\"Xiao-Shan Gao\"]","published":"2026-07-02T16:06:29Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.AC\"]","methods":"[]","has_code":false}