ECCC-Report TR19-032https://eccc.weizmann.ac.il/report/2019/032Comments and Revisions published for TR19-032en-usTue, 05 Mar 2019 10:51:04 +0200
Paper TR19-032
| Strongly Exponential Separation Between Monotone VP and Monotone VNP |
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2019/032We show that there is a sequence of explicit multilinear polynomials $P_n(x_1,\ldots,x_n)\in \mathbb{R}[x_1,\ldots,x_n]$ with non-negative coefficients that lies in monotone VNP such that any monotone algebraic circuit for $P_n$ must have size $\exp(\Omega(n)).$ This builds on (and strengthens) a result of Yehudayoff (2018) who showed a lower bound of $\exp(\tilde{\Omega}(\sqrt{n})).$Tue, 05 Mar 2019 10:51:04 +0200https://eccc.weizmann.ac.il/report/2019/032