Lower bounds for monotone arithmetic circuits via communication complexity

Valiant [Val80] 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 2 Ω(n 1/4 / log(n)) .

The polynomial P n embeds the SINK • XOR function devised recently by Chattopadhyay, Mande and Sherif [CMS20] 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 •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 setmultilinear polynomials f n,m such that both F n,m -•f n,m and F n,m + •f n,m have monotone circuit complexity 2 Ω(n/ log(n)) if ≥ 2 -Ω(m) and F n,m := n i=1 (x i,1 + • • • + x i,m ), 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š [Hru20] as a first step towards proving lower bounds against general cicuits via his new approach.