{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreidnd7y4ygz4ivkrd7lalxyx2zhqvsndnkqvkc6bqc24r6cpdvva3y",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mnz62pdh33w2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.12144v1",
  "publishedAt": "2026-06-11T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Ruichen Qiu",
    "Yichuan Cao",
    "Qiao-Long Huang",
    "Ruyong Feng",
    "Xiao-Shan Gao"
  ],
  "textContent": "**Authors:** Ruichen Qiu, Yichuan Cao, Qiao-Long Huang, Ruyong Feng, Xiao-Shan Gao\n\nIn this paper, we prove that output-sensitive sparse polynomial GCD computation over finite fields is NP-hard under BPP many-one reduction. More precisely, for two sparse univariate polynomials $f,g$ with finite field coefficients, there exists no randomized algorithm to compute $\\mathrm{gcd}(f,g)$, which is polynomial-time in the sizes of $f,g,\\gcd(f,g)$ under the standard complexity assumption $\\mathrm{NP}\\nsubseteq\\mathrm{BPP}$. This settles the open problem posed as Challenge 5 in The Sparsity Challenges in the finite field setting. Furthermore, we show that the Roots of Unity Detection problem over finite fields is NP-hard; that is, determining whether the GCD of a sparse univariate polynomial and $x^n - 1$ has nonzero degree is NP-hard.",
  "title": "Output-sensitive Sparse Polynomial GCD over Finite Fields is NP-hard"
}