Constant-depth circuits vs. monotone circuits

Bruno P. Cavalar, Igor C. Oliveira

We establish new separations between the power of monotone and general (non-monotone) Boolean circuits: - For every $k\ge 1$, there is a monotone function in $\mathsf{A}{\mathsf{C}}^0$ that re…