2026-07-24T05:42:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18299 2024-03-06T11:01:33Z ddc:004 open_access

Constant-Depth Circuits vs. Monotone Circuits Cavalar, Bruno P. Oliveira, Igor C. circuit complexity monotone circuit complexity bounded-depth circuis constraint-satisfaction problems We establish new separations between the power of monotone and general (non-monotone) Boolean circuits: - For every k ≥ 1, there is a monotone function in AC⁰ (constant-depth poly-size 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⁰[⊕] (constant-depth poly-size 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 constant-depth circuits can be more efficient than monotone formulas and monotone circuits when computing monotone functions. In the opposite direction, we observe that non-trivial 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)^{d-1}}. 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 Boolean-valued CSPs via their polymorphisms. This result and the consequences we derive from it might be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bruno P. Cavalar and Igor C. Oliveira 2023 Is Part Of LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2023.29 urn:nbn:de:0030-drops-182998 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.29 eng https://creativecommons.org/licenses/by/4.0/legalcode