{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreib7ywnfzsw3xoi57okfimfwneux5jgft3uwotwpobqnx74lag5yoa",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mpqzgl4nqem2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2607.02364v1",
  "publishedAt": "2026-07-03T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Qiao-Long Huang",
    "Yichuan Cao",
    "Ruichen Qiu",
    "Xiao-Shan Gao"
  ],
  "textContent": "**Authors:** Qiao-Long Huang, Yichuan Cao, Ruichen Qiu, Xiao-Shan Gao\n\nWe 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.",
  "title": "Deterministic Polynomial-time Exact-root Computation for Sparse Polynomials with Bounded Total Degree"
}