Abstract
We establish new separations between the power of monotone and general (nonmonotone) Boolean circuits:
 For every k ≥ 1, there is a monotone function in AC⁰ (constantdepth polysize circuits) that requires monotone circuits of depth Ω(log^k n). This significantly extends a classical result of Okol'nishnikova [Okol'nishnikova, 1982] and Ajtai and Gurevich [Ajtai and Gurevich, 1987]. In addition, our separation holds for a monotone graph property, which was unknown even in the context of AC⁰ versus mAC⁰.
 For every k ≥ 1, there is a monotone function in AC⁰[⊕] (constantdepth polysize circuits extended with parity gates) that requires monotone circuits of size exp(Ω(log^k n)). This makes progress towards a question posed by Grigni and Sipser [Grigni and Sipser, 1992]. These results show that constantdepth circuits can be more efficient than monotone formulas and monotone circuits when computing monotone functions.
In the opposite direction, we observe that nontrivial simulations are possible in the absence of parity gates: every monotone function computed by an AC⁰ circuit of size s and depth d can be computed by a monotone circuit of size 2^{n  n/O(log s)^{d1}}. We show that the existence of significantly faster monotone simulations would lead to breakthrough circuit lower bounds. In particular, if every monotone function in AC⁰ admits a polynomial size monotone circuit, then NC² is not contained in NC¹.
Finally, we revisit our separation result against monotone circuit size and investigate the limits of our approach, which is based on a monotone lower bound for constraint satisfaction problems (CSPs) established by Göös, Kamath, Robere and Sokolov [Göös et al., 2019] via lifting techniques. Adapting results of Schaefer [Thomas J. Schaefer, 1978] and Allender, Bauland, Immerman, Schnoor and Vollmer [Eric Allender et al., 2009], we obtain an unconditional classification of the monotone circuit complexity of Booleanvalued CSPs via their polymorphisms. This result and the consequences we derive from it might be of independent interest.
BibTeX  Entry
@InProceedings{cavalar_et_al:LIPIcs.CCC.2023.29,
author = {Cavalar, Bruno P. and Oliveira, Igor C.},
title = {{ConstantDepth Circuits vs. Monotone Circuits}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {29:129:37},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772822},
ISSN = {18688969},
year = {2023},
volume = {264},
editor = {TaShma, Amnon},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18299},
URN = {urn:nbn:de:0030drops182998},
doi = {10.4230/LIPIcs.CCC.2023.29},
annote = {Keywords: circuit complexity, monotone circuit complexity, boundeddepth circuis, constraintsatisfaction problems}
}
Keywords: 

circuit complexity, monotone circuit complexity, boundeddepth circuis, constraintsatisfaction problems 
Collection: 

38th Computational Complexity Conference (CCC 2023) 
Issue Date: 

2023 
Date of publication: 

10.07.2023 