{"id":"arxiv/2607.02364","url":"https://arxiv.org/abs/2607.02364","tags":["cs.DS","math.AC"],"score":0,"title":"Deterministic Polynomial-time Exact-root Computation for Sparse Polynomials with Bounded Total Degree","domain":"cs.DS","source":"arxiv","authors":["Qiao-Long Huang","Yichuan Cao","Ruichen Qiu","Xiao-Shan Gao"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-02","reactions":{}}