Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first qualitative improvement to this classical result: we construct a family of polynomials $P_n$ in $n$ variables, each of its monomials has positive coefficient, such that $P_n$ can be computed by a polynomial-size \emph{depth-three formula} but every monotone circuit computing it has size $2^{\Omega(n^{1/4}/\log(n))}$.

The polynomial $P_n$ embeds the $\text{SINK}\circ \text{XOR}$ function devised recently by Chattopadhyay, Mande and Sherif (2020) to refute the Log-Approximate-Rank Conjecture in communication complexity. To prove our lower bound for $P_n$, we develop a general connection between corruption of combinatorial rectangles by any function $f \circ \text{XOR}$ and corruption of product polynomials by a certain polynomial $P^f$ that is an arithmetic embedding of $f$. This connection should be of independent interest.

Using further ideas from communication complexity, we construct another family of set-multilinear polynomials $f_{n,m}$ such that both $F_{n,m} - \epsilon\cdot f_{n,m}$ and $F_{n,m} + \epsilon\cdot f_{n,m}$ have monotone circuit complexity $2^{\Omega(n/\log(n))}$ if $\epsilon \geq 2^{- \Omega( m )}$ and $F_{n,m} = \prod_{i=1}^n \big(x_{i,1} +\cdots+x_{i,m}\big)$, with $m = O( n/\log n )$. The polynomials $f_{n,m}$ have 0/1 coefficients and are in VNP. Proving such lower bounds for monotone circuits has been advocated recently by Hrubeš (2020) as a first step towards proving lower bounds against general circuits via his new approach.

Minor changes made in section 6. Proof of Lemma 6.1

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first qualitative improvement to this classical result: we construct a family of polynomials $P_n$ in $n$ variables, each of its monomials has positive coefficient, such that $P_n$ can be computed by a polynomial-size \emph{depth-three formula} but every monotone circuit computing it has size $2^{\Omega(n^{1/4}/\log(n))}$.

The polynomial $P_n$ embeds the $\text{SINK}\circ \text{XOR}$ function devised recently by Chattopadhyay, Mande and Sherif (2020) to refute the Log-Approximate-Rank Conjecture in communication complexity. To prove our lower bound for $P_n$, we develop a general connection between corruption of combinatorial rectangles by any function $f \circ \text{XOR}$ and corruption of product polynomials by a certain polynomial $P^f$ that is an arithmetic embedding of $f$. This connection should be of independent interest.

Using further ideas from communication complexity, we construct another family of set-multilinear polynomials $f_{n,m}$ such that both $F_{n,m} - \epsilon\cdot f_{n,m}$ and $F_{n,m} + \epsilon\cdot f_{n,m}$ have monotone circuit complexity $2^{\Omega(n/\log(n))}$ if $\epsilon \geq 2^{- \Omega( m )}$ and $F_{n,m} = \prod_{i=1}^n \big(x_{i,1} +\cdots+x_{i,m}\big)$, with $m = O( n/\log n )$. The polynomials $f_{n,m}$ have 0/1 coefficients and are in VNP. Proving such lower bounds for monotone circuits has been advocated recently by Hrubeš (2020) as a first step towards proving lower bounds against general circuits via his new approach.