Bootstrapping variables in algebraic circuits
Manindra Agrawal, Sumanta Ghosh, Nitin Saxena · Proceedings of the National Academy of Sciences · 2018
Significance Zero testing [or polynomial identity testing (PIT)] for circuits is a computational algebra problem with numerous practical applications and a beautiful theory (e.g., primality testing and graph matching are solved using PIT). It strongly relates to showing that there are explicit/natural polynomials that require exponentially large circuits. The latter is also called the algebraic version of the P ≠ NP question (or VP ≠ ?VNP) and lies in the intersection of mathematics and computing. This work provides a plausible route to it if we can design a polynomial-time computable, but small enough, hitting set for trivariate depth-4 circuits [merely Σ Π Σ ∧ ( 3 ) ].