Paper

{
  "raw_xml": "<entry>\n    <id>http://arxiv.org/abs/2602.20832v1</id>\n    <title>Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree</title>\n    <updated>2026-02-24T12:13:58Z</updated>\n    <link href='https://arxiv.org/abs/2602.20832v1' rel='alternate' type='text/html'/>\n    <link href='https://arxiv.org/pdf/2602.20832v1' rel='related' title='pdf' type='application/pdf'/>\n    <summary>We study deterministic polynomial identity testing (PIT) and reconstruction algorithms for depth-$4$ arithmetic circuits of the form \\[ Σ^{[r]}\\!\\wedge^{[d]}\\!Σ^{[s]}\\!Π^{[δ]}. \\] 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 $δ$. This model also includes algebraic representations that arise in tensor decomposition and moment-based learning tasks such as mixture models and subspace learning.\n  We give deterministic worst-case algorithms for PIT and reconstruction in this model. Our PIT construction applies when $d&gt;r^2$ and yields explicit hitting sets of size $O(r^4 s^4 n^2 d δ^3)$. The reconstruction algorithm runs in time $\\textrm{poly}(n,s,d)$ under the condition $d=Ω(r^4δ)$, and in particular it tolerates polynomially large top fan-in $r$ and bottom degree $δ$.\n  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.\n  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.</summary>\n    <category scheme='http://arxiv.org/schemas/atom' term='cs.CC'/>\n    <published>2026-02-24T12:13:58Z</published>\n    <arxiv:primary_category term='cs.CC'/>\n    <author>\n      <name>Amir Shpilka</name>\n    </author>\n    <author>\n      <name>Yann Tal</name>\n    </author>\n  </entry>"
}