Negations are powerful even in small depth

Bruno Cavalar, Théo Borém Fabris, Partha Mukhopadhyay +2

We study the power of negation in the Boolean and algebraic settings and show the following results. * We construct a family of polynomials $P_n$ in $n$ variables, all of whose mon…