Negations Are Powerful Even in Small Depth

We study the power of negation in the Boolean and algebraic settings and show the following results. 1. We construct a family of polynomials Pn in n variables, all of whose monomials have positive coefficients, such that Pn can be computed by a depth three circuit of polynomial size but any monotone circuit computing it has size 2Ω(n). This is the strongest possible separation result between monotone and non-monotone arithmetic computations and improves upon all earlier results, including the seminal work of Valiant (1980) and more recently by Chattopadhyay, Datta, and Mukhopadhyay (2021). We then boot-strap this result to prove strong monotone separations for polynomials of constant degree, which solves an open problem from the survey of Shpilka and Yehudayoff (2010). 2. By moving to the Boolean setting, we can prove superpolynomial monotone Boolean circuit lower bounds for specific Boolean functions, which imply that all the powers of certain monotone polynomials cannot be computed by polynomially sized monotone arithmetic circuits. This leads to a new kind of monotone vs. non-monotone separation in the arithmetic setting. 3. We then define a collection of problems with linear-algebraic nature, which are similar to span programs, and prove monotone Boolean circuit lower bounds for them. In particular, this gives the strongest known monotone lower bounds for functions in uniform (non-monotone) NC2. Our construction also leads to an explicit matroid that defines a monotone function that is difficult to compute, which solves an open problem by Jukna and Seiwert (2020) in the context of the relative powers of greedy and pure dynamic programming algorithms. Our monotone arithmetic and Boolean circuit lower bounds are based on known techniques, such as reduction from monotone arithmetic complexity to multipartition communication complexity and the approximation method for proving lower bounds for monotone Boolean circuits, but we overcome several new challenges in order to obtain efficient upper bounds using low-depth circuits.