Description

Title: Constant-depth circuits vs. monotone circuits

Speaker: Bruno Cavalar

Abstract: We establish strong separations between the power of monotone and general (non-monotone) Boolean circuits: - For every $k \geq 1$, there is a monotone function in $\mathsf{AC^0}$ (constant-depth poly-size circuits) that requires monotone circuits of depth $\Omega(\log^k n)$. This vastly extends a classical result of Okol'nishnikova (1982) and Ajtai and Gurevich (1987). Our separation holds for a monotone graph property, which was unknown even in the context of $\mathsf{AC}^0$ versus $\mathsf{mAC}^0$. - For every $k \geq 1$, there is a monotone function in $\mathsf{AC^0}[\oplus]$ (constant-depth poly-size circuits extended with parity gates) that requires monotone circuits of size $\exp(\Omega(\log^k n))$. This makes progress towards a question posed by Grigni and Sipser (1992). These results show that constant-depth circuits can be considerably more efficient than 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 $\mathsf{AC}^0$ 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 stronger monotone simulations would lead to breakthrough circuit lower bounds. In particular, if every monotone function in $\mathsf{AC}^0$ admits a polynomial size monotone circuit, then $\mathsf{NC}^2$ is not contained in $\mathsf{NC}^1$. 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 established by Göös et al. (2019) via lifting techniques. Adapting results of Schaefer (1978) and Allender et al. (2009), we obtain a 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.

All scheduled dates:

Upcoming

No Upcoming activities yet

Past