{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreibsea5rrmer6krrrnlefgzoz2lm4v5bdaxepuhjpdy7wt36h3qmg4",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mgqry7edmfd2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2603.07589v1",
  "publishedAt": "2026-03-10T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Aminadav Chuyoon",
    "Amir Shpilka"
  ],
  "textContent": "**Authors:** Aminadav Chuyoon, Amir Shpilka\n\nWe study sparse polynomials with bounded individual degree and their factors, obtaining the following structural and algorithmic results. 1. A deterministic polynomial-time algorithm to find all sparse divisors of a sparse polynomial of bounded individual degree, together with the first upper bound on the number of non-monomial irreducible factors of such polynomials. 2. A $\\mathrm{poly}(n,s^{d\\log \\ell})$-time algorithm that recovers $\\ell$ irreducible $s$-sparse polynomials of individual degree at most $d$ from blackbox access to their (not necessarily sparse) product. This partially resolves a question of Dutta-Sinhababu-Thierauf (RANDOM 2024). In particular, if $\\ell=O(1)$ the algorithm runs in polynomial time. 3. Deterministic algorithms for factoring a product of $s$-sparse polynomials of individual degree $d$ from blackbox access. Over fields of characteristic zero or sufficiently large characteristic the runtime is $\\mathrm{poly}(n,s^{d^3\\log n})$; over arbitrary fields it is $\\mathrm{poly}(n,(d^2)!,s^{d^5\\log n})$. This improves Bhargava-Saraf-Volkovich (JACM 2020), which gives $\\mathrm{poly}(n,s^{d^7\\log n})$ time for a single sparse polynomial. For a single sparse input we obtain $\\mathrm{poly}(n,s^{d^2\\log n})$ time. 4. Given blackbox access to a product of factors of sparse polynomials of bounded individual degree, we give a deterministic polynomial-time algorithm to find all irreducible sparse multiquadratic factors with multiplicities. This generalizes the algorithms of Volkovich (RANDOM 2015, 2017) and extends the complete-power test of Bisht-Volkovich (CC 2025). To handle arbitrary fields we introduce a notion of primitive divisors that removes characteristic assumptions from most of our algorithms.",
  "title": "On Factorization of Sparse Polynomials of Bounded Individual Degree"
}