Monotone Arithmetic Circuit Lower Bounds Via Communication Complexity

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 *depth-three* formula but every monotone circuit computing it has size exp(n^{1/4}/log(n)).