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, which achieves only a quasi-polynomial dependence on the input parameters, our algorithm is \textit{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.
Blogger's Review: This paper presents an efficient algorithm to address the computation of roots for multivariate sparse polynomials, particularly demonstrating superior polynomial time complexity under bounded total degree constraints. The clarity in complexity analysis and the insight into the sparsity of the base polynomial are significant, warranting further research and application in computational algebraic geometry.