{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreigmcjbfgev2k4x52h73vk7nywtbfekwkeunsd6htocrocahrjcqnu",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mpdr5qejvtq2"
  },
  "path": "/report/2026/108",
  "publishedAt": "2026-06-28T06:27:45.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "We design a deterministic algorithm that, given blackbox access to the product $f=\\prod_{i=1}^{\\ell}{h_i}$ of $\\ell$ irreducible $s$-sparse $n$-variate polynomials of bounded individual degree $d$, over fields of characteristic zero, and more generally over fields of sufficiently large positive characteristic, recovers the $h_i$'s and their multiplicities in time $\\mathrm{poly}(n,(s\\ell d)^d)$. For any constant $d>2$, this is the first \\emph{polynomial-time} algorithm for this problem, resolving for the bounded-individual-degree regime an open question of Dutta, Sinhababu, and Thierauf (Random 2026). The previous best deterministic algorithm, due to the authors, runs in $\\mathrm{poly}(n,d^d,s^{d\\log \\ell},\\ell^d)$ time, which is quasi-polynomial in $\\ell$. The improvement is enabled by a new sparse rational interpolation theorem in the bounded-individual-degree setting, based on reconstructing the denominator from its logarithmic derivatives. Given blackbox access to rational functions $a_1/b,\\ldots,a_N/b$ where the $a_j$'s and $b$ are $s$-sparse of individual degree at most $d$ with $\\gcd(a_1,\\ldots,a_N,b)=1$, we recover the $a_j$'s and $b$ in time $\\mathrm{poly}(n,d!,s^d,N)$. In contrast to the rational interpolation theorem of Chuyoon-Shpilka (2026), our algorithm reconstructs the denominator directly and does not require a precomputed list of its irreducible factors.",
  "title": "TR26-108 |  Factoring Products of Sparse Irreducibles of Bounded Individual Degree via  Rational Interpolation | \n\n\tAmir Shpilka, \n\n\tAminadav Chuyoon"
}