ECCC-Report TR20-187https://eccc.weizmann.ac.il/report/2020/187Comments and Revisions published for TR20-187en-usSun, 13 Dec 2020 16:31:53 +0200
Paper TR20-187
| If VNP is hard, then so are equations for it |
Mrinal Kumar,
C Ramya,
Ramprasad Saptharishi,
Anamay Tengse
https://eccc.weizmann.ac.il/report/2020/187Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP *does not* have efficiently computable equations. In other words, any nonzero polynomial that vanishes on the coefficient vectors of all polynomials in the class VNP requires algebraic circuits of super-polynomial size.
In a recent work of Chatterjee and the authors (FOCS 2020), it was shown that the subclasses of VP and VNP consisting of polynomials with bounded integer coefficients *do* have equations with small algebraic circuits. Their work left open the possibility that these results could perhaps be extended to all of VP or VNP. The results in this paper show that assuming the hardness of Permanent, at least for VNP, allowing polynomials with large coefficients does indeed incur a significant blow up in the circuit complexity of equations.Sun, 13 Dec 2020 16:31:53 +0200https://eccc.weizmann.ac.il/report/2020/187