{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreiey52y4zswrn4hnb5vo3wtiey5zk6fo7tsznsuphsfs4pebownh7i",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mfmcvd356c52"
  },
  "path": "/report/2026/029",
  "publishedAt": "2026-02-24T10:49:42.000Z",
  "site": "https://eccc.weizmann.ac.il",
  "textContent": "We study deterministic polynomial identity testing (PIT) and reconstruction algorithms for depth-$4$ arithmetic circuits of the form \\\\[ \\Sigma^{[r]}\\\\!\\wedge^{[d]}\\\\!\\Sigma^{[s]}\\\\!\\Pi^{[\\delta]}. \\\\] This model generalizes Waring decompositions and diagonal circuits, and captures sums of powers of low-degree sparse polynomials. Specifically, each circuit computes a sum of $r$ terms, where each term is a $d$-th power of an $s$-sparse polynomial of degree $\\delta$. This model also includes algebraic representations that arise in tensor decomposition and moment-based learning tasks such as mixture models and subspace learning. We give deterministic worst-case algorithms for PIT and reconstruction in this model. Our PIT construction applies when $d>r^2$ and yields explicit hitting sets of size $O(r^4 s^4 n^2 d \\delta^3)$. The reconstruction algorithm runs in time $\\textrm{poly}(n,s,d)$ under the condition $d=\\Omega(r^4\\delta)$, and in particular it tolerates polynomially large top fan-in $r$ and bottom degree $\\delta$. Both results hold over fields of characteristic zero and over fields of sufficiently large characteristic. These algorithms provide the first polynomial-time deterministic solutions for depth-$4$ powering circuits with unbounded top fan-in. In particular, the reconstruction result improves upon previous work which required non-degeneracy or average-case assumptions. The PIT construction relies on the ABC theorem for function fields (Mason-Stothers theorem), which ensures linear independence of high-degree powers of sparse polynomials after a suitable projection. The reconstruction algorithm combines this with Wronskian-based differential operators, structural properties of their kernels, and a robust version of the Klivans-Spielman hitting set.",
  "title": "TR26-029 |  Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree | \n\n\tAmir Shpilka, \n\n\tYann Tal"
}