__
Revision #1 to TR19-032 | 31st July 2020 08:15
__
#### Strongly Exponential Separation Between Monotone VP and Monotone VNP

**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.

__
TR19-032 | 4th March 2019 18:21
__

#### Strongly Exponential Separation Between Monotone VP and Monotone VNP

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