License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2023.29
URN: urn:nbn:de:0030-drops-182998
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18299/
Go to the corresponding LIPIcs Volume Portal


Cavalar, Bruno P. ; Oliveira, Igor C.

Constant-Depth Circuits vs. Monotone Circuits

pdf-format:
LIPIcs-CCC-2023-29.pdf (1 MB)


Abstract

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.

BibTeX - Entry

@InProceedings{cavalar_et_al:LIPIcs.CCC.2023.29,
  author =	{Cavalar, Bruno P. and Oliveira, Igor C.},
  title =	{{Constant-Depth Circuits vs. Monotone Circuits}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{29:1--29:37},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/18299},
  URN =		{urn:nbn:de:0030-drops-182998},
  doi =		{10.4230/LIPIcs.CCC.2023.29},
  annote =	{Keywords: circuit complexity, monotone circuit complexity, bounded-depth circuis, constraint-satisfaction problems}
}

Keywords: circuit complexity, monotone circuit complexity, bounded-depth circuis, constraint-satisfaction problems
Collection: 38th Computational Complexity Conference (CCC 2023)
Issue Date: 2023
Date of publication: 10.07.2023


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI