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,\dots ,x_n)\in \mathbb{R}[x_1,\dots ,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})).$

11 pages, to appear in ACM TOCT; new version adds references to results of Kuznetsov, Kasim-Zade, Gashkov and Sergeev

Cited by in corpus (2)

• Monotone Circuit Lower Bounds from Robust Sunflowers
• Limitations of Sums of Bounded-Read Formulas