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

arXiv: https://arxiv.org/abs/2607.02364 · HTML: https://mlsanity.com/paper/2607.02364/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 2 Jul 2026.

## Built on by (most cited first, 1 of 1)

- [MechMath Agent Team: LLM Driven Agents for Mathematical Research](https://mlsanity.com/paper/2607.04394/) (2026)

## Abstract (arXiv)

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.