Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR19-032 | 31st July 2020 08:15

Strongly Exponential Separation Between Monotone VP and Monotone VNP

RSS-Feed




Revision #1
Authors: Srikanth Srinivasan
Accepted on: 31st July 2020 08:15
Downloads: 38
Keywords: 


Abstract:

We 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})).$



Changes to previous version:

Added references to results of Kuznetsov, Kasim-Zade, Gashkov and Sergeev. Also added more detailed proof outline. Some typos/small errors corrected.


Paper:

TR19-032 | 4th March 2019 18:21

Strongly Exponential Separation Between Monotone VP and Monotone VNP





TR19-032
Authors: Srikanth Srinivasan
Publication: 5th March 2019 10:51
Downloads: 440
Keywords: 


Abstract:

We 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})).$



ISSN 1433-8092 | Imprint