Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > NIMROD KAPLAN:
All reports by Author Nimrod Kaplan:

TR26-076 | 14th May 2026
Nimrod Kaplan, Amir Shpilka

Polynomial Identity Testing for Read-4 Arithmetic Formulas

We present the first algorithms for polynomial identity testing (PIT) of read-$4$ arithmetic formulas in the non-multilinear setting. Specifically, we give a polynomial-time PIT algorithm in the whitebox model and a quasi-polynomial-time algorithm in the blackbox model. Since our techniques are based on proving hardness of representation results, we extend ... more >>>




ISSN 1433-8092 | Imprint