Agrawal, Manindra ; Ghosh, Sumanta ; Saxena, Nitin (2019) Bootstrapping variables in algebraic circuits Proceedings of the National Academy of Sciences of the United States of America, 116 (17). pp. 8107-8118. ISSN 0027-8424
Full text not available from this repository.
Official URL: http://doi.org/10.1073/pnas.1901272116
Related URL: http://dx.doi.org/10.1073/pnas.1901272116
Abstract
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)].
| Item Type: | Article |
|---|---|
| Source: | Copyright of this article belongs to National Academy of Sciences. |
| ID Code: | 122735 |
| Deposited On: | 12 Aug 2021 11:40 |
| Last Modified: | 12 Aug 2021 11:40 |
Repository Staff Only: item control page
