Lower bounds for monotone arithmetic circuits via communication complexity

Valiant (1980) showed that general arithmetic circuits with negation can be exponentially more powerful than monotone ones. We give the first improvement to this classical result: we construct a family of polynomials P n in n variables, each of its monomials has non-negative 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 (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 ∘ 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 − є· 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 ∏ i =1 n ( 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š (2020) as a first step towards proving lower bounds against general circuits via his new approach.

Authors

• Arkadev Chattopadhyay
• Rajit Datta
• Partha Mukhopadhyay

Keywords

• Communication Complexity
• Lower Bounds
• Monotone Arithmetic Circuits