Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > YANN TAL:
All reports by Author Yann Tal:

TR26-029 | 24th February 2026
Amir Shpilka, Yann Tal

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree

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 ... more >>>




ISSN 1433-8092 | Imprint