# Constant-Depth Circuits vs. Monotone Circuits

Bruno P. Cavalar111Email<EMAIL_ADDRESS>
Department of Computer Science
University of Warwick Igor C. Oliveira222Email<EMAIL_ADDRESS>
Department of Computer Science
University of Warwick

###### Abstract

We establish new 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 significantly extends a classical result of
Okol’nishnikova [49] and Ajtai and Gurevich [3]. In addition, 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 [33].

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 $\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 faster 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 (CSPs) established by Göös, Kamath,
Robere and Sokolov [31] via lifting techniques. Adapting results of Schaefer
[67] and Allender, Bauland, Immerman, Schnoor and Vollmer [2], 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.

###### Contents

  1. 1 Introduction
    1. 1.1 Results
      1. 1.1.1 Constant-depth circuits vs. monotone circuits
      2. 1.1.2 Non-trivial monotone simulations and their consequences
      3. 1.1.3 Monotone complexity of constraint satisfaction problems
    2. 1.2 Techniques
    3. 1.3 Directions and open problems
  2. 2 Preliminaries
    1. 2.1 Notation
    2. 2.2 Background results
  3. 3 Constant-Depth Circuits vs. Monotone Circuits
    1. 3.1 A monotone size lower bound for a function in $\mathsf{AC}^{0}[\oplus]$
    2. 3.2 A monotone depth lower bound for a graph property in $\mathsf{AC}^{0}$
    3. 3.3 Efficient monotone padding for graph properties
  4. 4 Non-Trivial Monotone Simulations and Their Consequences
    1. 4.1 A non-trivial simulation for bounded-depth circuits
    2. 4.2 Non-monotone lower bounds from monotone simulations
  5. 5 Monotone Complexity of Constraint Satisfaction Problems
    1. 5.1 Definitions
    2. 5.2 Basic facts about $\mathsf{CSP}\text{-}\mathsf{SAT}$
    3. 5.3 A monotone dichotomy for $\mathsf{CSP}\text{-}\mathsf{SAT}$
    4. 5.4 Some auxiliary results
    5. 5.5 Consequences for monotone circuit lower bounds via lifting
  6. A A Lower Bound for $\mathsf{3\mbox{-}XOR\mbox{-}SAT}$ Using the Approximation Method
  7. B Schaefer’s Theorem in Monotone Complexity
    1. B.1 Connectivity and generation functions
    2. B.2 Proof of reduction lemmas
    3. B.3 Monotone circuit upper bounds
  8. C Background on Post’s Lattice and Clones

##  1 Introduction

A Boolean function $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is monotone if $f(x)\leq
f(y)$ whenever $x_{i}\leq y_{i}$ for each coordinate $1\leq i\leq n$. Monotone
Boolean functions, and the monotone Boolean circuits333Recall that in a
monotone Boolean circuit the gate set is limited to
$\left\\{\mathsf{AND},\mathsf{OR}\right\\}$ and input gates are labelled by
elements from $\\{x_{1},\ldots,x_{n},0,1\\}$. that compute them, have been
extensively investigated for decades due to their relevance in circuit
complexity [56], cryptography [15], learning theory [17], proof complexity
[43, 54], property testing [28], pseudorandomness [25], optimisation [30],
hazard-free computations [37], and meta-complexity [35], among other topics.
In addition, over the last few years a number of results have further
highlighted the importance of monotone complexity as a central topic in the
study of propositional proofs, total search problems, communication protocols,
and related areas (see [26] for a recent survey).

Some of the most fundamental results about monotone functions deal with their
complexities with respect to different classes of Boolean circuits, such as
the monotone circuit lower bound of Razborov [57] for $\mathsf{Matching}$ and
the constant-depth circuit lower bound of Rossman [62] for
$k$-$\mathsf{Clique}$. Particularly important to our discussion is a related
strand of research that contrasts the computational power of monotone circuits
relative to general (non-monotone) $\mathsf{AND}$/$\mathsf{OR}$/$\mathsf{NOT}$
circuits, which we review next.

##### Weakness of Monotone Circuits.

The study of monotone simulations of non-monotone computations and associated
separation results has a long and rich history. In a sequence of celebrated
results, [57, 8, 1, 69] showed the existence of monotone functions that can be
computed by circuits of polynomial size but require monotone circuits of size
$2^{n^{\Omega(1)}}$. In other words, the use of negations can significantly
speedup the computation of monotone functions. More recently, Göös, Kamath,
Robere and Sokolov [31] considerably strengthened this separation by showing
that some monotone functions in $\mathsf{NC}^{2}$ (poly-size
$O(\log^{2}n)$-depth fan-in two circuits) require monotone circuits of size
$2^{n^{\Omega(1)}}$. (An earlier weaker separation against monotone depth
$n^{\Omega(1)}$ was established in [66].) Therefore, negations can also allow
monotone functions to be efficiently computed in parallel.

Similar separations about the limitations of monotone circuits are also known
at the low-complexity end of the spectrum: Okol’nishnikova [49] and
(independently) Ajtai and Gurevich [3] exhibited monotone functions in
$\mathsf{AC}^{0}$ (i.e., constant-depth poly-size
$\mathsf{AND}$/$\mathsf{OR}$/$\mathsf{NOT}$ circuits) that require monotone
$\mathsf{AC}^{0}$ circuits (composed of only $\mathsf{AND}$/$\mathsf{OR}$
gates) of super-polynomial size.444We refer to [16] for an alternate
exposition of this result. This result has been extended to an exponential
separation in [24], which shows the existence of a monotone function in
$\mathsf{AC}^{0}$ that requires monotone depth-$d$ circuits of size
$2^{\widetilde{\Omega}(n^{1/d})}$ even if $\mathsf{MAJ}$ (majority) gates are
allowed in addition to $\mathsf{AND}$/$\mathsf{OR}$ gates.555Separations
between monotone and non-monotone devices have also been extensively
investigated in other settings. This includes average-case complexity [14],
different computational models, such as span programs [13, 65] and algebraic
complexity (see [20] and references therein), and separations in first-order
logic [68, 45, 46]. We restrict our attention to worst-case separations for
Boolean circuits in this paper.

##### Strength of Monotone Circuits.

In contrast to these results, in many settings negations do not offer a
significant speedup and monotone computations can be unexpectedly powerful.
For instance, monotone circuits are able to efficiently implement several non-
trivial algorithms, such as solving constraint satisfaction problems using
treewidth bounds (see, e.g., [50, Chapter 3]). As another example, in the
context of cryptography, it has been proved that if one-way functions exist,
then there are monotone one-way functions [29]. Below we describe results that
are more closely related to the separations investigated in our paper.

In the extremely constrained setting of depth-$2$ circuits, Quine [55] showed
that monotone functions computed by size-$s$ $\mathsf{DNFs}$ (resp.,
$\mathsf{CNFs}$) can always be computed by size-$s$ monotone $\mathsf{DNFs}$
(resp., $\mathsf{CNFs}$). Some results along this line are known for larger
circuit depth, but with respect to more structured classes of monotone Boolean
functions. Rossman [61, 64] showed that any homomorphism-preserving graph
property computed by $\mathsf{AC}^{0}$ circuits is also computed by monotone
$\mathsf{AC}^{0}$ circuits.666A function
$f:\left\\{0,1\right\\}^{\binom{n}{2}}\to\left\\{0,1\right\\}$ is called a
_graph property_ if $f(G)=f(H)$ whenever $G$ and $H$ are isomorphic graphs,
and _homomorphism-preserving_ if $f(G)\leq f(H)$ whenever there is a graph
homomorphism from $G$ to $H$. It is easy to see that every homomorphism-
preserving graph property is monotone. Under no circuit depth restriction,
Berkowitz [12] proved that the monotone and non-monotone circuit size
complexities of every slice function are polynomially related.777A function
$f:\left\\{0,1\right\\}^{\binom{n}{2}}\to\left\\{0,1\right\\}$ is a _slice
function_ if there is $i\geq 0$ such that $f(x)$ is $0$ on inputs of Hamming
weight less than $i$ and $1$ on inputs of Hamming weight larger than $i$.

Despite much progress and sustained efforts, these two classes of results
leave open tantalising problems about the power of cancellations in
computation.888Any non-monotone circuit can be written as an $\mathsf{XOR}$
(parity) of distinct monotone sub-circuits (see, e.g., [32, Appendix A.1]), so
negations can be seen as a way of combining, or cancelling, different monotone
computations. See also a related discussion in Valiant [71]. In particular,
they suggest the following basic question about the contrast between the
weakness of monotone computations and the strength of negations:

_What is the largest computational gap between the power of monotone and
general _(_ non-monotone _)_ Boolean circuits?_

A concrete formalisation of this question dates back to the seminal work on
monotone complexity of Grigni and Sipser [33] in the early nineties. They
asked if there are monotone functions in $\mathsf{AC}^{0}$ that require super-
polynomial size monotone Boolean circuits, i.e., if
$\mathsf{AC}^{0}\cap\mathsf{Mono}\nsubseteq\mathsf{mSIZE}[\mathsf{poly}]$. In
case this separation holds, it would exhibit the largest qualitative gap
between monotone and general Boolean circuits, i.e., even extremely parallel
non-monotone computations can be more efficient than arbitrary monotone
computations.

###  1.1 Results

Our results show that, with respect to the computation of monotone functions,
highly parallel (non-monotone) Boolean circuits can be super-polynomially more
efficient than unrestricted monotone circuits. Before providing a precise
formulation of these results, we introduce some notation.

For a function $d\colon\mathbb{N}\to\mathbb{N}$, let
$\mathsf{m}\mathsf{DEPTH}[d]$ denote the class of Boolean functions computed
by monotone fan-in two $\mathsf{AND}/\mathsf{OR}$ Boolean circuits of depth
$O(d(n))$. Similarly, we use $\mathsf{m}\mathsf{SIZE}[s]$ to denote the class
of Boolean functions computed by monotone circuits of size $O(s(n))$. More
generally, for a circuit class $\mathcal{C}$, we let $\mathsf{m}\mathcal{C}$
denote its natural monotone analogue. Finally, for a Boolean function
$f\colon\\{0,1\\}^{n}\to\\{0,1\\}$, we use $\mathsf{mSIZE}({f})$ and
$\mathsf{mDEPTH}({f})$ to denote its monotone circuit size and depth
complexities, respectively. We refer to Jukna [42] for standard background on
circuit complexity theory.

#### 1.1.1. Constant-depth circuits vs. monotone circuits

Recall that the Okol’nishnikova-Ajtai-Gurevich [49, 3] theorem states that
$\mathsf{AC}^{0}\cap\mathsf{Mono}\nsubseteq\mathsf{mAC}^{0}$. In contrast, as
our main result, we establish a separation between constant-depth Boolean
circuits and monotone circuits of much larger depth. In particular, we show
that constant-depth circuits with negations can be significantly more
efficient than monotone formulas.

######  Theorem 1.1 (Polynomial-size constant-depth vs. larger monotone
depth).

For every $k\geq 1$, we have
$\mathsf{AC}^{0}\cap\mathsf{Mono}\not\subseteq\mathsf{m}\mathsf{DEPTH}[(\log
n)^{k}]$. Moreover, this separation holds for a monotone graph property.

In a more constrained setting, Kuperberg [45, 46] exhibited a monotone graph
property expressible in first-order logic that cannot be expressed in positive
first-order logic. A separation that holds for a monotone graph property was
unknown even in the context of $\mathsf{AC}^{0}$ versus $\mathsf{mAC}^{0}$.

Let $\mathsf{HomPreserving}$ denote the class of all homomorphism-preserving
graph properties, and recall that Rossman [61, 64] established that
$\mathsf{AC}^{0}\cap\mathsf{HomPreserving}\subseteq\mathsf{mAC}^{0}$. Theorem
1.1 implies that this efficient monotone simulation does not extend to the
larger class of monotone graph properties, even if super-logarithmic depth is
allowed.

Our argument is completely different from those of [49, 3, 16, 24] and their
counterparts in first-order logic [68, 45, 46]. In particular, it allows us to
break the $O(\log n)$ monotone depth barrier present in previous separations
with an $\mathsf{AC}^{0}$ upper bound, which rely on lower bounds against
monotone circuits of depth $d$ and size (at most) $2^{n^{O(1/d)}}$. We defer
the discussion of our techniques to Section 1.2.

In our next result, we consider monotone circuits of unbounded depth.

######  Theorem 1.2 (Polynomial-size constant-depth vs. larger monotone size).

For every $k\geq 1$, we have
$\mathsf{AC}^{0}[\oplus]\cap\mathsf{Mono}\not\subseteq\mathsf{m}\mathsf{SIZE}[2^{(\log
n)^{k}}]$.

Theorem 1.1 and Theorem 1.2 are incomparable: while the monotone lower bound
is stronger in the latter, its constant-depth upper bound requires parity
gates. Theorem 1.2 provides the first separation between constant-depth
circuits and monotone circuits of polynomial size, coming remarkably close to
a solution to the question considered by Grigni and Sipser [33].

We note that in both of our results the family of monotone functions is
explicit and has a simple description (see Section 1.2).

#### 1.1.2. Non-trivial monotone simulations and their consequences

While Theorem 1.1 and Theorem 1.2 provide more evidence for the existence of
monotone functions in $\mathsf{AC}^{0}$ which require monotone circuits of
super-polynomial size, they still leave open the intriguing possibility that
unbounded fan-in $\oplus$-gates might be crucial to achieve the utmost
cancellations (speedups) provided by constant-depth circuits. This further
motivates the investigation of efficient monotone simulations of constant-
depth circuits without parity gates, which we consider next.

For convenience, let $\mathsf{AC}^{0}_{d}[s]$ denote the class of Boolean
functions computed by $\mathsf{AC}^{0}$ circuits of depth $\leq d$ and size
$\leq s(n)$. (We might omit $s(n)$ and/or $d$ when implicitly quantifying over
all families of polynomial size circuits and/or all constant depths.)

We observe that a non-trivial monotone simulation is possible in the absence
of parity gates. Indeed, by combining existing results from circuit complexity
theory, it is not hard to show that
$\mathsf{AC}^{0}_{d}[s]\cap\mathsf{Mono}\subseteq\mathsf{m}\mathsf{SIZE}[2^{n(1-{1/O(\log
s)^{d-1}})}]$ (see Section 4.1). Moreover, this upper bound is achieved by
monotone $\mathsf{DNFs}$ of the same size. This is the best upper bound we can
currently show for the class of all monotone functions when the depth $d\geq
3$. (Negations offer no speedup at depths $d\leq 2$ [55].) In contrast, we
prove that a significantly faster monotone simulation would lead to new (non-
monotone) lower bounds in complexity theory. Recall that it is a notorious
open problem to obtain explicit lower bounds against depth-$d$ circuits of
size $2^{\omega(n^{1/(d-1)})}$, for any fixed $d\geq 3$. We denote by
$\mathsf{GraphProperties}$ the set of all Boolean functions which are graph
properties.

######  Theorem 1.3 (New circuit lower bounds from monotone simulations).

There exists $\varepsilon>0$ such that the following holds.

  1. 1.

If $\mathsf{AC}^{0}_{3}\cap\mathsf{Mono}\subseteq\mathsf{m}\mathsf{NC}^{1}$,
then $\mathsf{NP}\not\subseteq\mathsf{AC}^{0}_{3}[2^{o(n)}]$.

  2. 2.

If
$\mathsf{AC}^{0}_{4}\cap\mathsf{Mono}\subseteq\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$,
then $\mathsf{NP}\not\subseteq\mathsf{AC}^{0}_{4}[2^{o(\sqrt{n}/\log n)}]$.

  3. 3.

If
$\mathsf{AC}^{0}\cap\mathsf{Mono}\subseteq\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$,
then $\mathsf{NC}^{2}\not\subseteq\mathsf{NC}^{1}$.

  4. 4.

If
$\mathsf{NC}^{1}\cap\mathsf{Mono}\subseteq\mathsf{m}\mathsf{SIZE}[2^{O(n^{\varepsilon})}]$,
then $\mathsf{NC}^{2}\not\subseteq\mathsf{NC}^{1}$.

  5. 5.

If
$\mathsf{AC}^{0}\cap\mathsf{Mono}\cap\mathsf{GraphProperties}\subseteq\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$,
then $\mathsf{NP}\not\subseteq\mathsf{NC}^{1}$.

  6. 6.

If
$\mathsf{NC}^{1}\cap\mathsf{Mono}\cap\mathsf{GraphProperties}\subseteq\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$,
then $\mathsf{L}\not\subseteq\mathsf{NC}^{1}$.

Item (3) of Theorem 1.3 implies in particular that, if the upper bound of
Theorem 1.2 cannot be improved to $\mathsf{AC}^{0}$ (i.e., the question asked
by [33] has a negative answer), then
$\mathsf{NC}^{2}\not\subseteq\mathsf{NC}^{1}$. It also improves a result from
[21] showing the weaker conclusion $\mathsf{NP}\nsubseteq\mathsf{NC}^{1}$
under the same assumption.

Even if it’s impossible to efficiently simulate $\mathsf{AC}^{0}$ circuits
computing monotone functions using unbounded depth monotone circuits, it could
still be the case that a simulation exists for certain classes of monotone
functions with additional structure. As explained above, Rossman’s result [61,
64] achieves this for graph properties that are preserved under homomorphisms.
Items (5) and (6) of Theorem 1.3 show that a simulation that holds for all
monotone graph properties is sufficient to get new separations in
computational complexity.

#### 1.1.3. Monotone complexity of constraint satisfaction problems

Recall that [31] showed the existence of a monotone function
$f^{\mathsf{GKRS}}$ in $\mathsf{NC}^{2}$ that is not in
$\mathsf{m}\mathsf{SIZE}[2^{n^{\Omega(1)}}]$. As opposed to classical results
[57, 8, 1, 69] that rely on the approximation method, their monotone circuit
lower bound employs a lifting technique from communication complexity. It is
thus natural to consider if their approach can be adapted to provide a
monotone function $g$ that is efficiently computable by constant-depth
circuits but is not in $\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$.

As remarked in [31, 26], all monotone lower bounds obtained from lifting
theorems so far also hold for monotone encodings of constraint satisfaction
problems (CSPs). Next, we introduce a class of monotone Boolean functions
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ which capture the framework and lower
bound of [31].

Encoding CSPs as monotone Boolean functions. Let
$R\subseteq\left\\{0,1\right\\}^{k}$ be a relation. We call $k$ the _arity_ of
$R$. Let $V=(i_{1},\dots,i_{k})\in[n]^{k}$, and let
$f_{R,V}:\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ be the function that
accepts a string $x\in\left\\{0,1\right\\}^{n}$ if
$(x_{i_{1}},\dots,x_{i_{k}})\in R$. We call $f_{R,V}$ a _constraint
application_ of $R$ on $n$ variables. (A different choice of the sequence $V$
gives a different constraint application of $R$.) If $S$ is a finite set of
Boolean relations, we call any set of constraint applications of relations
from $S$ on a fixed set of variables an _$S$ -formula._ In particular, we can
describe an $S$-formula through a set of pairs $(V,R)$. We say that an
$S$-formula $F$ is _satisfiable_ if there exists an assignment to the
variables of $F$ which satisfies all the constraints of $F$.

Let $S=\left\\{R_{1},\dots,R_{k}\right\\}$ be a finite set of Boolean
relations. Let $\ell_{i}$ be the arity of the relation $R_{i}$. Note that
there are $n^{\ell_{i}}$ possible constraint applications of the relation
$R_{i}$ on $n$ variables. Let $N:=\sum_{i=1}^{k}n^{\ell_{i}}$. We can identify
each $S$-formula $F$ on a fixed set of $n$ variables with a corresponding
string $w^{F}\in\left\\{0,1\right\\}^{N}$, where $w^{F}_{j}=1$ if and only if
the $j$-th possible constraint application (corresponding to one of the $N$
pairs $(V,R))$ appears in $F$. Let
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}^{n}:\left\\{0,1\right\\}^{N}\to\left\\{0,1\right\\}$
be the Boolean function which accepts a given $S$-formula $F$ if $F$ is
_unsatisfiable_. Note that this is a monotone function. When $n$ is clear from
the context or we view $\\{\mathsf{CSP}\text{-}\mathsf{SAT}_{S}^{n}\\}_{n\geq
1}$ as a sequence of functions, we simply write
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$.

The function $f^{\mathsf{GKRS}}$ from [31] is simply
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ for
$S=\\{\oplus^{0}_{3},\oplus^{1}_{3}\\}$, where
$\oplus^{b}_{3}(x_{1},x_{2},x_{3})=1$ if and only if
$\sum_{i}x_{i}=b~{}(\mathsf{mod}~{}2)$. More generally, for any finite set $S$
of Boolean relations, their framework shows how to lift a Resolution width
(resp. depth) lower bound for an arbitrary unsatisfiable $S$-formula $F$ over
$m$ variables into a corresponding monotone circuit size (resp. depth) lower
bound for $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}^{n}$, where
$n=\mathsf{poly}(m)$.

Despite the generality of the technique from [31] and the vast number of
possibilities for $S$, we prove that a direct application of their approach
cannot establish Theorem 1.1 and Theorem 1.2. This is formalised as follows.
(We refer to Section 5 for much stronger forms of the result.)

######  Theorem 1.4 (Limits of the direct approach via lifting and CSPs).

Let $S$ be a finite set of Boolean relations. The following holds.

  1. 1.

If
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\notin\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$
then $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is $\oplus\mathsf{L}$-hard under
$\leq^{\mathsf{AC}^{0}}_{m}\\!$ reductions.

  2. 2.

If $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\notin\mathsf{m}\mathsf{NC}^{1}$ then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is $\mathsf{L}$-hard under
$\leq^{\mathsf{AC}^{0}}_{m}\\!$ reductions.

In particular, since there are functions (e.g., $\mathsf{Majority}$)
computable in logarithmic space that are not in $\mathsf{AC}^{0}[\oplus]$,
Theorem 1.4 (Part 2) implies that any $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$
function that is hard for poly-size monotone formulas
($\mathsf{m}\mathsf{NC}^{1}$) must lie outside $\mathsf{AC}^{0}[\oplus]$.
Observe that this can also be interpreted as a _monotone simulation_ : for any
finite set $S$ of Boolean relations, if
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\in\mathsf{AC}^{0}[\oplus]$ then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\in\mathsf{m}\mathsf{NC}^{1}$.999 Jumping
ahead, our proof of Theorem 1.2 still relies in a crucial way on the monotone
lower bound obtained by [31]. However, our argument requires an extra
ingredient and does not follow from a direct application of their template. We
provide more details about it in Section 1.2 below. Interestingly, the proof
of Theorem 1.1 was discovered by trying to avoid the “barrier” posed by
Theorem 1.4.

Theorem 1.4 is a corollary of a general result that completely classifies the
monotone circuit complexity of Boolean-valued constraint satisfaction problems
based on the set $\mathsf{Pol}(S)$ of _polymorphisms_ of $S$, a standard
concept in the investigation of CSPs.101010Roughly speaking, $\mathsf{Pol}(S)$
captures the amount of symmetry in $S$, and a larger set $\mathsf{Pol}(S)$
implies that solving $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is computationally
easier. We refer the reader to Section 5 for more details and for a discussion
of Post’s lattice, which is relevant in the next statement. We present next a
simplified version of this result, which shows a dichotomy for the monotone
circuit size and depth of Boolean-valued constraint satisfaction problems. We
refer to Section 5 for a more general formulation and additional consequences.

######  Theorem 1.5 (Dichotomies for the monotone complexity of Boolean-valued
CSPs).

Let $S$ be a finite set of Boolean relations. The following holds.

  1. 1.

_Monotone Size Dichotomy:_ If $\mathsf{Pol}(S)\subseteq\mathrm{L_{3}}$ there
is $\varepsilon>0$ such that
$\mathsf{mSIZE}({\mathsf{CSP}\text{-}\mathsf{SAT}_{S}})=2^{\Omega(n^{\varepsilon})}$.
Otherwise, $\mathsf{mSIZE}({\mathsf{CSP}\text{-}\mathsf{SAT}_{S}})=n^{O(1)}$.

  2. 2.

_Monotone Depth Dichotomy:_ If $\mathsf{Pol}(S)\subseteq\mathrm{L_{3}}$ or
$\mathsf{Pol}(S)\subseteq\mathrm{V_{2}}$ or
$\mathsf{Pol}(S)\subseteq\mathrm{E_{2}}$, there is $\varepsilon>0$ such that
$\mathsf{mDEPTH}({\mathsf{CSP}\text{-}\mathsf{SAT}_{S}})={\Omega(n^{\varepsilon})}$.
Otherwise, $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\in\mathsf{m}\mathsf{NC}^{2}$.

We note that previous papers of Schaefer [67] and Allender, Bauland, Immerman,
Schnoor and Vollmer [2] provided a _conditional_ classification of the
complexity of such CSPs. Theorem 1.5 and its extensions, which build on their
results and techniques, paint a complete and _unconditional_ picture of their
monotone complexity.111111 We remark that only recently has Schaefer’s
classification been extended to the non-Boolean case [72, 18]. Though the
refined classification of [2] is conjectured to hold analogously in the case
of non-Boolean CSPs [48], this is still open (see the discussion in [19,
Section 7]).

###  1.2 Techniques

Our arguments combine in novel ways several previously unrelated ideas from
the literature. The exposition below follows the order in which the results
appear above, except for the overview of the proof of Theorem 1.1, which
appears last. We discuss this result after explaining the proof of Theorem 1.2
and the classification of the monotone complexity of CSPs (Theorem 1.4 and
Theorem 1.5), as this sheds light into how the proof of Theorem 1.1 was
discovered and into the nature of the argument.

##### A monotone circuit size lower bound for a function in
$\mathsf{AC}^{0}[\oplus]$.

We first give an overview of the proof of Theorem 1.2.

###### The lower bound of _[31]_.

We begin by providing more details about the aforementioned monotone circuit
lower bound of [31], since their result is a key ingredient in our separation
(see [26] for a more detailed overview). Recall that their function
$f^{\mathsf{GKRS}}$ corresponds to $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ for
$S=\\{\oplus^{0}_{3},\oplus^{1}_{3}\\}$. Following their notation, this is
simply the Boolean function
$\mathsf{3\mbox{-}XOR\mbox{-}SAT}_{n}\colon\left\\{0,1\right\\}^{2n^{3}}\to\left\\{0,1\right\\}$
which uses each input bit to indicate the presence of a linear equation with
exactly $3$ variables. This (monotone) function accepts a given linear system
over ${\mathbb{F}}_{2}$ if the system is _unsatisfiable_. As one of their main
results, [31] employed a lifting technique from communication complexity to
show the existence of a constant $\varepsilon>0$ such that
$\mathsf{m}\mathsf{SIZE}(\mathsf{3\mbox{-}XOR\mbox{-}SAT}_{n})=2^{n^{\varepsilon}}$.
(We show in Appendix A that a weaker super-polynomial monotone circuit size
lower bound for $\mathsf{3\mbox{-}XOR\mbox{-}SAT}_{n}$ can also be obtained
using the approximation method and a reduction.)

_Sketch of the proof of Theorem 1.2._ Since
$\mathsf{3\mbox{-}XOR\mbox{-}SAT}_{n}\in\mathsf{NC}^{2}$ (see, e.g, [31]),
their result implies that
$\mathsf{NC}^{2}\cap\mathsf{Mono}\nsubseteq\mathsf{m}\mathsf{SIZE}[2^{n^{\Omega(1)}}]$.
On the other hand, we are after a separation between _constant-depth_ (non-
monotone) circuits and _polynomial-size_ (unbounded depth) monotone circuits.
There are two natural ways that one might try to approach this challenge, as
discussed next.

First, the lifting framework explored by [31] offers in principle the
possibility that by carefully picking a different set $S$ of Boolean
relations, one might be able to reduce the non-monotone depth complexity of
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ while retaining super-polynomial
monotone hardness. However, Theorem 1.4 shows that this is impossible, as
explained above.

A second possibility is to combine the _exponential_ $2^{n^{\varepsilon}}$
monotone circuit size lower bound for $\mathsf{3\mbox{-}XOR\mbox{-}SAT}_{n}$
and a padding argument, since we only need _super-polynomial_ hardness.
Indeed, this argument can be used to define a monotone function
$g\colon\\{0,1\\}^{n}\to\\{0,1\\}$ that is computed by polynomial-size fan-in
two circuits of depth $\mathsf{poly}(\log\log n)$ but requires monotone
circuit of size $n^{\omega(1)}$. However, it is clear that no padding argument
alone can reduce the non-monotone circuit depth bound to $O(1)$ while
retaining the desired monotone hardness.

Given that both the classical widely investigated approximation method for
monotone lower bounds and the more recent lifting technique do not appear to
work in their current forms, for some time it seemed to us that, if true, a
significantly new technique would be needed to establish a separation similar
to the one in Theorem 1.2.

Perhaps surprisingly, it turns out that a more clever approach that combines
padding with a non-trivial circuit upper bound can be used to obtain the
result. The first key observation, already present in [31] and other papers,
is that $\mathsf{3\mbox{-}XOR\mbox{-}SAT}_{n}$ can be computed not only in
$\mathsf{NC}^{2}$ but actually by polynomial-size span programs over
${\mathbb{F}}_{2}$. On the other hand, it is known that this model is
equivalent in power to parity branching programs [47], which correspond to the
non-uniform version of $\oplus\mathsf{L}$, i.e., counting modulo $2$ the
number of accepting paths of a nondeterministic Turing machine that uses
$O(\log n)$ space. A second key idea is that such a computation can be
simulated by $\mathsf{AC}^{0}[\oplus]$ circuits of sub-exponential size and
large depth. More precisely, similarly to an existing simulation of
$\mathsf{NL}$ (nondeterministic logspace) by $\mathsf{AC}^{0}$ circuits of
depth $d$ and size $2^{n^{O(1/d)}}$ via a “guess-and-verify” approach, it is
possible to achieve an analogous simulation of $\oplus\mathsf{L}$ using
$\mathsf{AC}^{0}[\oplus]$ circuits (this folklore result appears implicit in
[6] and [51]). Putting everything together, it follows that for a large enough
but constant depth, $\mathsf{3\mbox{-}XOR\mbox{-}SAT}_{n}$ can be computed by
$\mathsf{AC}^{0}[\oplus]$ circuits of size $2^{n^{\varepsilon/2}}$. Since this
function is hard against monotone circuits of size $2^{n^{\varepsilon}}$, a
padding argument can now be used to establish a separation between
$\mathsf{AC}^{0}[\oplus]$ and $\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$. (A
careful choice of parameters provides the slightly stronger statement in
Theorem 1.2.)

##### Non-trivial monotone simulations and their consequences.

In order to conclude that significantly stronger monotone simulations imply
new complexity separations (Theorem 1.3), we argue contrapositively. By
supposing a complexity collapse, we can exploit known monotone circuit lower
bounds to conclude that a hard monotone function exists in a lower complexity
class. For instance, if $\mathsf{NC}^{2}\subseteq\mathsf{NC}^{1}$, then
$\mathsf{3\mbox{-}XOR\mbox{-}SAT}\in\mathsf{NC}^{1}$, and we can conclude by
standard depth-reduction for $\mathsf{NC}^{1}$ and padding, together with the
exponential lower bound for $\mathsf{3\mbox{-}XOR\mbox{-}SAT}$ due to [31],
that there exists a monotone function in $\mathsf{AC}^{0}$ which is hard for
polynomial-size monotone circuits. The other implications are argued in a
similar fashion. In particular, we avoid the more complicated use of hardness
magnification from [21] to establish this kind of result, while also getting a
stronger consequence.

A little more work is required in the case of graph properties (Theorem 1.3
Items 5 and 6), as padding the function computing a graph property does not
yield a graph property. We give a general lemma that allows us to pad monotone
graph properties while preserving their structure (Lemma 3.6). We then argue
as in the case for general functions, using known monotone lower bounds for
graph properties. We note that Lemma 3.6 is also important in the proof of
Theorem 1.1, which will be discussed below. We believe that our padding
technique for graph properties might find additional applications.

##### Monotone complexity of CSPs.

These are the most technical results of the paper. Since explaining the
corresponding proofs requires more background and case analysis, here we only
briefly describe the main ideas and references behind Theorem 1.4, Theorem
1.5, and the extensions discussed in Section 5.

A seminal work of Schaefer [67] proved that any Boolean CSP is either solvable
in polynomial-time or it is $\mathsf{NP}$-complete. Later, Jeavons [39]
observed that the complexity of deciding if a given set of constraint
applications of $S$ is satisfiable depends exclusively on the set
$\mathsf{Pol}(S)$ of _polymorphisms_ of $S$. Intuitively, the set of
polymorphisms of a set of relations is a measure of its symmetry. The more
symmetric a set of relations is, the lesser is its expressive power. Jeavons
formally proves this intuition by showing that, if
$\mathsf{Pol}(S)\subseteq\mathsf{Pol}(S^{\prime})$, then the problem of
deciding the satisfiability of a given $S^{\prime}$-formula can be reduced in
polynomial-time to that of deciding the satisfiability of a given $S$-formula.
This allows Jeavons to reprove Schaefer’s result.

Existing proofs and classification results for constraint satisfaction
problems do not encode the satisfiability problem as a monotone Boolean
function $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$, in the way we described
above. We reexamine Schaefer’s and Jeavons’s proofs and establish that the
reduction from $\mathsf{CSP}\text{-}\mathsf{SAT}_{S^{\prime}}$ to
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ can also be done with efficient
monotone circuits. Making use of and adapting parts of the refined results and
analysis of [2], which builds on the earlier dichotomy result of [67] and
provides a detailed picture of the computational complexity of Boolean-valued
CSPs, we prove in fact that the underlying reductions can all be done in
monotone nondeterministic logspace.

Finally, using known upper and lower bounds for monotone circuits together
with a direct analysis of some basic cases, and inspecting Post’s lattice [52,
9, 10], we are able to show that $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is
hard for monotone circuits only when $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is
$\oplus\mathsf{L}$-complete, as in Theorem 1.4 Part 1.

##### A monotone circuit depth lower bound for a function in
$\mathsf{AC}^{0}$.

Next, we combine insights obtained from the monotone lower bound of [31], our
proof of Theorem 1.2 via a guess-and-verify depth reduction and padding, and
the statement of Theorem 1.4 (limits of the direct approach via CSPs) to get
the separation in Theorem 1.1. As alluded to above, our approach differs from
those of [49, 3, 16, 24] and related results in the context of first-order
logic [68, 45, 46].

Recall that the [31] framework lifts a Resolution width lower bound for an
unsatisfiable $S$-formula $F$ into a corresponding monotone circuit size lower
bound for $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$. On the other hand, Theorem
1.4 rules out separating constant-depth circuits from monotone circuits of
polynomial size via $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ functions. In
particular, we cannot directly apply the chain of reductions from [31] to
obtain the desired separation result. Instead, we extract from the specific
$S$-formula $F$ that they use a _structural property_ that will allow us to
improve the $\mathsf{AC}^{0}[\oplus]$ upper from Theorem 1.2 to the desired
$\mathsf{AC}^{0}$ upper bound in Theorem 1.1.

In [31] the formula $F$ is a _Tseitin_ contradiction, a well-known class of
unsatisfiable CNFs with a number of applications in proof complexity. For an
undirected graph $G$, the Tseitin formula $T(G)$ encodes a system of linear
equations modulo $2$ as follows: each edge $e\in E(G)$ becomes a Boolean
variable $x_{e}$, and each vertex $v\in V(G)$ corresponds to a constraint
(linear equation) $C_{v}$ stating that $\sum_{u\in
N_{G}(v)}x_{\\{v,u\\}}=1~{}(\mathsf{mod}\;2)$, where $N_{G}(v)$ denotes the
set of neighbours of $v$ in $G$. Crucially, $T(G)$ does not encode an
arbitrary system of linear equations, i.e., the following key structural
property holds: every variable $x_{e}$ appears in exactly $2$ equations.

On a technical level, this property is not preserved when obtaining a (total)
monotone function $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ by the gadget
composition employed in the lifting framework and its reductions. However, we
can still hope to explore this property in a somewhat different argument with
the goal of obtaining CSP instances that lie in a complexity class weaker than
$\oplus\mathsf{L}$, which is the main bottleneck in the proof of Theorem 1.2
yielding $\mathsf{AC}^{0}[\oplus]$ circuits instead of $\mathsf{AC}^{0}$. At
the same time, considering this structural property immediately takes us
outside the domain of Theorem 1.4, which does not impose structural conditions
over the CSP instances.

We can capture the computational problem corresponding to this type of system
of linear equations using the following Boolean function. Let
$\mathsf{OddFactor}_{n}:\left\\{0,1\right\\}^{\binom{n}{2}}\to\left\\{0,1\right\\}$
be the function that accepts a given graph $G$ if the formula $T(G)$ described
above is _satisfiable_. (Equivalently, if $G$ admits a spanning subgraph in
which the degree of every vertex is odd.) Note that $\mathsf{OddFactor}_{n}$
is a monotone Boolean function: adding edges to $G$ cannot make a satisfiable
system unsatisfiable, since we can always set a new edge variable $x_{e}$ to
$0$.

While $\mathsf{3\mbox{-}XOR\mbox{-}SAT}$ (the corresponding
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ function obtained from an appropriate
Tseitin formula via the framework of [31]) admits a $\oplus\mathsf{L}$ upper
bound, we observe that $\mathsf{OddFactor}_{n}$ can be computed in
$\mathsf{L}$ thanks to its more structured class of input instances. Indeed,
one can prove that the formula $T(G)$ is satisfiable if and only if every
connected component of G has an even number of vertices.121212A simple parity
argument shows that odd-sized components cannot be satisfied. On the other
hand, we can always satisfy an even-sized component by starting with an
arbitrary assignment, which must satisfy an even number of constraints by a
parity argument, and flipping the values of the edges in a path between
unsatisfied nodes, until all nodes in the connected component are satisfied.
In turn, the latter condition can be checked in logarithmic space using
Reingold’s algorithm for undirected $s$-$t$-connectivity [58]. (We note that
related ideas appear in an unpublished note of Johannsen [41].) This is the
first application of Reingold’s algorithm to this kind of separation.

At the same time, $\mathsf{OddFactor}_{n}$ retains at least part of the
monotone hardness of $\mathsf{3\mbox{-}XOR\mbox{-}SAT}$. Using a different
reduction from a communication complexity lower bound, [13] proved that the
monotone circuit depth of $\mathsf{OddFactor}_{n}$ is $n^{\Omega(1)}$.
Altogether, we obtain a monotone Boolean function (indeed a graph property)
that lies in $\mathsf{L}$ but is not in $\mathsf{m}\mathsf{DEPTH}[n^{o(1)}]$.
Applying a guess-and-verify depth reduction for $\mathsf{L}$ and using (graph)
padding (analogously to the proof sketch of Theorem 1.2), we get a monotone
graph property in $\mathsf{AC}^{0}$ that is not in
$\mathsf{m}\mathsf{DEPTH}[\log^{k}n]$. This completes the sketch of the proof
of Theorem 1.1.

###  1.3 Directions and open problems

Constant-depth circuits and monotone circuits are possibly the two most widely
investigated models in circuit complexity theory. Although our results provide
new insights about the relation between them, there are exceptionally basic
questions that remain open.

While [55] showed that negations can be efficiently eliminated from circuits
of depth $d\leq 2$ that compute monotone functions, already at depth $d=3$ the
situation is much less clear. Theorem 4.3 (see Section 4.1) implies that every
monotone function in depth-$3$ $\mathsf{AC}^{0}$ admits a monotone circuit of
size $2^{n-\Omega(n/\log^{2}n)}$. It is unclear to us if this is optimal.
While [24] rules out an efficient _constant-depth_ monotone simulation, it is
still possible (and consistent with Theorem 1.1) that
$\mathsf{AC}^{0}_{3}\cap\mathsf{Mono}\subseteq\mathsf{mNC}^{1}$. Is there a
significantly better monotone circuit size upper bound for monotone functions
computed by polynomial-size depth-$3$ circuits?

Our results come close to solving the question posed by Grigni and Sipser
[33]. Using our approach, it would be sufficient to show that
$\mathsf{OddFactor}_{n}$ requires monotone circuits of size
$\exp(n^{\Omega(1)})$. This is closely related to the challenge of obtaining
an exponential monotone circuit size lower bound for $\mathsf{Matching}_{n}$,
a longstanding open problem in monotone complexity (see [42, Section
9.11]).131313Note that in $\mathsf{OddFactor}$ we are concerned with the
existence of a spanning subgraph where the degree of every vertex is odd,
while in $\mathsf{Matching}$ the degree should be exactly $1$. Indeed, it’s
possible to reduce $\mathsf{OddFactor}$ to $\mathsf{Matching}$ using monotone
$\mathsf{AC}^{0}$ circuits (see [5, Lemma 6.18]).

Incidentally, the algebraic complexity variant of the $\mathsf{AC}^{0}$ vs.
$\mathsf{mSIZE}[\mathsf{poly}]$ problem has been recently settled in a strong
way through a new separation result obtained by Chattopadhyay, Datta, and
Mukhopadhyay [20]. Could some of their techniques be useful to attack the more
elusive Boolean case?

Finally, it would be interesting to develop a more general theory able to
explain when cancellations can speedup the computation of monotone Boolean
functions. Our investigation of monotone simulations and separations for
different classes of monotone functions (graph properties and constraint
satisfaction problems) can be seen as a further step in this direction.

Acknowledgements. We thank Arkadev Chattopadhyay for several conversations
about the $\mathsf{AC}^{0}$ versus $\mathsf{mSIZE}[\mathsf{poly}]$ problem and
related questions. We are also grateful to Denis Kuperberg for explaining to
us the results from [45, 46]. The first author thanks Ninad Rajgopal for
helpful discussions about depth reduction. Finally, we thank Gernot Salzer for
the code used to generate Figures 1, 2, and 3. This work received support from
the Royal Society University Research Fellowship
URF$\setminus$R1$\setminus$191059, the EPSRC New Horizons Grant EP/V048201/1,
and the Centre for Discrete Mathematics and its Applications (DIMAP) at the
University of Warwick.

##  2 Preliminaries

###  2.1 Notation

###### Boolean functions.

We denote by $\mathsf{Mono}$ the set of all monotone Boolean functions. We
define $\mathsf{poly}=\left\\{n\mapsto n^{C}:C\in{\mathbb{N}}\right\\}$. A
Boolean function
$f:\left\\{0,1\right\\}^{\binom{n}{2}}\to\left\\{0,1\right\\}$ is said to be a
graph property if $f(G)=f(H)$ for any two isomorphic graphs $G$ and $H$. Let
${\mathcal{F}}=\left\\{f_{n}\right\\}_{n\in{\mathbb{N}}}$ be a sequence of
graph properties, where $f_{n}$ is defined over undirected graphs on $n$
vertices. We say that ${\mathcal{F}}$ is _preserved under homomorphisms_ if,
whenever there is a homomorphism from a graph $G$ to a graph $H$, we have
${\mathcal{F}}(G)\leq{\mathcal{F}}(H)$. We denote by $\mathsf{HomPreserving}$
the set of all graph properties which are preserved under homomorphisms. Note
that $\mathsf{HomPreserving}\subseteq\mathsf{Mono}$.

###### Boolean circuits.

We denote by $\mathsf{AC}^{0}_{d}[s]$ the family of Boolean functions computed
by size-$s$, depth-$d$ Boolean circuits with unbounded fan-in
$\left\\{\land,\lor\right\\}$-gates and input literals from
$\\{x_{1},\overline{x_{1}},\ldots,x_{n},\overline{x_{n}}\\}$. We write
$\mathsf{AC}^{0}[s]$ as a shorthand for
$\bigcup_{d=1}^{\infty}\mathsf{AC}^{0}_{d}[s]$, and $\mathsf{AC}^{0}$ as a
shorthand of $\mathsf{AC}^{0}[n^{O(1)}]=\mathsf{AC}^{0}[\mathsf{poly}]$. We
will also refer to $\mathsf{AC}^{0}_{d}[\mathsf{poly}]$ by
$\mathsf{AC}^{0}_{d}$. We write $\mathsf{DNF}[s]$ to denote the family of
Boolean functions computed by size-$s$ DNFs, where size is measured by number
of terms. We write $\mathsf{CNF}[s]$ analogously. We write $\mathsf{SIZE}[s]$
to denote the family of Boolean functions computed by size-$s$ circuits. We
write $\mathsf{DEPTH}[d]$ to denote the family of Boolean functions computed
by fan-in 2 circuits of depth $d$. We denote by $\mathsf{AC}^{0}[\oplus]$ the
family of Boolean functions computed by polynomial-size $\mathsf{AC}^{0}$
circuits with unbounded fan-in $\oplus$-gates.

We denote by $\mathsf{L}$ the family of Boolean functions computed by logspace
machines, and by $\mathsf{NL}$ the family of Boolean functions computed by
polynomial-time nondeterministic logspace machines. Moreover, we denote by
$\oplus\mathsf{L}$ the family of Boolean functions computed by polynomial-time
nondeterministic logspace machines with a _parity_ acceptance condition (i.e.,
an input is accepted if the number of accepting paths is odd).

###### Circuit complexity.

Given a circuit class ${\mathcal{C}}$, we write $\mathsf{m}C$ to denote the
monotone version of ${\mathcal{C}}$. Given a function $f$, we write
$\mathsf{mSIZE}({f})$ to denote the size of the smallest monotone circuit
computing $f$ and $\mathsf{mDEPTH}({f})$ to denote the smallest depth of a
fan-in 2 monotone circuit computing $f$. Given two Boolean functions $f,g$, we
write $f\leq^{\mathsf{mProj}}_{m}g$ if there exists a many-one reduction from
$f$ to $g$ in which each bit of the reduction is a monotone projection141414A
monotone projection is a projection without negations. of the input.

###### Miscellanea.

Let $\alpha\in\left\\{0,1\right\\}^{n}$ . We define
$\lvert\alpha\rvert_{1}:=\sum_{i=1}^{n}\alpha_{i}$. We call
$\lvert\alpha\rvert_{1}$ the _Hamming weight_ of $\alpha$. We let
$\operatorname{supp}(\alpha)=\left\\{i\in[n]:\alpha_{i}=1\right\\}$. We let
$\operatorname{THR}_{k,n}:\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ be
the Boolean function such that $\operatorname{THR}_{k,n}(x)=1\iff\lvert
x\rvert_{1}\geq k$.

###  2.2 Background results

The next lemma, which is proved via a standard “guess-and-verify” approach,
shows that nondeterministic logspace computations can be simulated by circuits
of size $2^{n^{\varepsilon}}$ and of depth $d=O_{\varepsilon}(1)$.

######  Lemma 2.1 (Folklore; see, e.g., [4, Lemma 8.1]).

For all $\varepsilon>0$, we have
$\mathsf{NL}\subseteq\mathsf{AC}^{0}[2^{n^{\varepsilon}}]$.

##  3 Constant-Depth Circuits vs. Monotone Circuits

In this section, we prove Theorems 1.2 and 1.1. For the upper bounds, we
require the logspace graph connectivity algorithm due to [58] and the
$\oplus\mathsf{L}$ algorithm for solving linear systems over $\mathbb{F}_{2}$
due to [11], as well as the depth-reduction techniques of [6, 4]. On the lower
bounds side, our proofs rely on previous monotone circuit and depth lower
bounds from [13, 31]. In order to obtain a monotone formula lower bound for a
graph property, we prove a graph padding lemma in Section 3.2.

###  3.1 A monotone size lower bound for a function in
$\mathsf{AC}^{0}[\oplus]$

In this section, we prove Theorem 1.2. We first recall the monotone circuit
lower bound of [31] and a depth-reduction lemma implicit in [6] and [51],
whose full proof we give below for completeness. We remark that similar
arguments can be employed to prove Lemma 2.1, essentially by replacing the
$\oplus$ gates by $\lor$ gates.

As explained in Section 1.2, in its strongest form the separation result from
[31] can be stated as follows.

######  Theorem 3.1 ([31]).

There exists $\varepsilon>0$ such that
$\oplus\mathsf{L}\cap\mathsf{Mono}\not\subseteq\mathsf{m}\mathsf{SIZE}[2^{o(n^{\varepsilon})}]$.
Moreover, this separation is witnessed by $\mathsf{3\mbox{-}XOR\mbox{-}SAT}$.

######  Lemma 3.2 (Folklore; see, e.g., [6, 51]).

Let $f:\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ be a Boolean function
computed by a $\oplus\mathsf{L}$ machine. For every $\delta>0$, there exists
an $\mathsf{AC}^{0}[\oplus]$ circuit of size $2^{n^{\delta}}$ that computes
$f$.

###### Proof.

Let $M$ be a $\oplus\mathsf{L}$-machine computing $f$. Without loss of
generality, we may assume that each configuration in the configuration graph
$G$ of $M$ is _time-stamped_ – in other words, each configuration carries the
information of the number of computational steps it takes to arrive at
it.151515Formally, we can define a $\oplus\mathsf{L}$-machine $M^{\prime}$
such that the configurations of $M^{\prime}$ are $(C,t)$, where $C$ is a
configuration of $M$, and $t=0,1,\dots,m=n^{O(1)}$ is a number denoting the
time in which the configuration was achieved. A configuration $(C,t)$ can only
reach a configuration $(C^{\prime},t+1)$ in the configuration graph of
$M^{\prime}$.  We may also assume that every accepting computation takes
exactly the same amount of time, which means that every path from the starting
configuration $v_{\mathsf{start}}$ to the accepting configuration
$v_{\mathsf{accept}}$ has the same length in the configuration graph. These
assumptions imply that the configuration graph is _layered_ (because a
configuration with time-stamp $t$ can only point to configurations with time-
stamp $t+1$) and acyclic. Note that, for a fixed machine, the configuration
graph can be computed from the input string using a projection.

Let $m=n^{O(1)}$ be the time that an accepting computation takes. We now show
how to count (modulo 2) the number of accepting paths from
$v_{\mathsf{start}}$ to $v_{\mathsf{accept}}$ with a depth-$d$
$\mathsf{AC}^{0}[\oplus]$ circuit. First, choose $m^{1/d}-1$ configurations
$v_{1},\dots,v_{m^{1/d}-1}$ (henceforth called “checkpoints”) from $V(G)$,
such that the configuration $v_{i}$ is at the level $i\cdot m^{1-1/d}$ in the
configuration graph (i.e., it takes $i\cdot m^{1-1/d}$ time steps to arrive at
$v_{i}$). For convenience, we let $v_{0}=v_{\mathsf{start}}$ and
$v_{m^{1/d}}=v_{\mathsf{accept}}$. We then count the number of paths from from
$v_{\mathsf{start}}$ to $v_{\mathsf{accept}}$ that go through
$v_{1},\dots,v_{m^{1/d}-1}$, and sum over all possible choices of the
checkpoints. Since the graph is layered and each path from $v_{0}$ to
$v_{m^{1/d}}$ has length exactly $m$, there is only one choice of checkpoints
that witnesses a given path from $v_{0}$ to $v_{m^{1/d}}$, so no path is
counted twice in this summation. Letting $\\#\mathsf{paths}(s,t,\ell)$ denote
the number of paths between configurations $s$ and $t$ with distance exactly
$\ell$, we obtain

$\\#\mathsf{paths}(v_{0},v_{m^{1/d}},m)=\sum_{v_{1},\dots,v_{m^{1/d}-1}}\prod_{i=0}^{m^{1/d}-1}\\#\mathsf{paths}(v_{i},v_{i+1},m^{1-1/d}).$

The above calculation can be done in modulo 2 with an unbounded fan-in XOR
gate (replacing the summation) and an unbounded fan-in AND gate (replacing the
product). Note that the formula above is recursive. Repeating the same
computation for calculating (modulo 2) the expression
$\\#\mathsf{paths}(v_{i},v_{i+1},m^{1-1/d})$ for each $i$, we obtain a
depth-$2d$ $\mathsf{AC}^{0}[\oplus]$ circuit for calculating the number of
paths from $v_{\mathsf{start}}$ to $v_{\mathsf{accept}}$ (modulo 2). Clearly,
the total size of the circuit is $2^{O(m^{1/d}\cdot\log m)}$, which is smaller
than $2^{n^{\delta}}$ for a large enough constant $d$. ∎

We now restate Theorem 1.2 and prove it by combining Theorems 3.1 and 3.2 with
a padding trick.

See 1.2

###### Proof.

By Theorem 3.1, there exists $\varepsilon>0$ and a monotone function
$f\in\oplus\mathsf{L}$ such that any monotone circuit computing $f$ has size
$2^{\Omega(n^{\varepsilon})}$.

Let $\delta=\varepsilon/k$ and let $m=2^{n^{\delta}}$. Let
$g:\left\\{0,1\right\\}^{n}\times\left\\{0,1\right\\}^{m}\to\left\\{0,1\right\\}$
be the Boolean function defined as $g(x,y)=f(x)$. Note that $g$ is a function
on $N:=m+n=2^{\Theta(n^{\delta})}$ bits. By Lemma 3.2, there exists an
$\mathsf{AC}^{0}[\oplus]$ circuit computing $f$ of size
$2^{n^{\delta}}=N^{O(1)}$. The same circuit computes $g$. On the other hand,
any monotone circuit computing $g$ has size
$2^{\Omega(n^{\varepsilon})}=2^{\Omega((\log
N)^{\varepsilon/\delta})}=2^{\Omega((\log N)^{k})}$. ∎

###  3.2 A monotone depth lower bound for a graph property in
$\mathsf{AC}^{0}$

In this section, we prove Theorem 1.1. We prove moreover that the function
that separates $\mathsf{AC}^{0}\cap\mathsf{Mono}$ and
$\mathsf{m}\mathsf{NC}^{i}$ can be taken to be a graph property. We state our
result in its full generality below.

######  Theorem 3.3.

For every $i\geq 1$, we have
$\mathsf{AC}^{0}\cap\mathsf{Mono}\cap\mathsf{GraphProperties}\not\subseteq\mathsf{m}\mathsf{DEPTH}[(\log
n)^{i}]$. In particular, we have
$\mathsf{AC}^{0}\cap\mathsf{Mono}\cap\mathsf{GraphProperties}\not\subseteq\mathsf{m}\mathsf{NC}^{i}$.

First, we recall a result of [13], which proves monotone lower bounds for the
following function. Let
$\mathsf{OddFactor}_{n}:\left\\{0,1\right\\}^{\binom{n}{2}}\to\left\\{0,1\right\\}$
be the function that accepts a given graph if it contains an _odd factor_ – in
other words, a spanning subgraph in which the degree of every vertex is odd.
Babai, Gál and Wigderson [13] proved the following result:

######  Theorem 3.4 ([13]).

Any monotone formula computing $\mathsf{OddFactor}_{n}$ has size
$2^{\Omega(n)}$, and any monotone circuit computing $\mathsf{OddFactor}_{n}$
has size $n^{\Omega(\log n)}$.

The proof in [13] is actually for the case of _bipartite graphs_ , but it
easily extends to general graphs, since the bipartite case reduces to the
general case by a monotone projection. The formula lower bound stated above is
slightly stronger because it makes use of asymptotically optimal lower bounds
on the randomized communication complexity of $\mathsf{DISJ}_{n}$ [44], which
were not available to [13]. We remark that, with a different language, a
monotone circuit lower bound for $\mathsf{OddFactor}$ is also implicitly
proved in Feder and Vardi [27, Theorem 30].

We now recall an upper bound for $\mathsf{OddFactor}$, implicitly proved in an
unpublished note due to Johannsen [41].

######  Theorem 3.5 ([41]).

We have $\mathsf{OddFactor}\in\mathsf{L}$.

###### Proof.

We first recall the following observation about the $\mathsf{OddFactor}$
function, which appears in different forms in the literature (see [70, Lemma
4.1] or [42, Lemma 18.16]; see also [41, Proposition 1] for a different
proof.)

######  Claim.

A graph $G$ has an odd factor if and only if every connected component of $G$
has an even number of vertices.

###### Proof.

If a graph $G$ has an odd factor, we can conclude that every connected
component of $G$ has an even number of vertices from the well-known
observation that in every graph there is an even number of vertices of odd
degree.

Now suppose that every connected component of $G$ has an even number of
vertices. We will iteratively construct an odd factor $F$ of $G$. We begin
with the empty graph. We take any two vertices $u,v$ in the same connected
component of $G$ which currently have even degree in $F$, and consider any
path $P=(x_{1},\dots,x_{k})$ between $u$ and $v$, where $x_{1}=u$ and
$x_{k}=v$. If the edge $x_{i}x_{i+1}$ is currently in $F$, we remove
$x_{i}x_{i+1}$ from $F$; otherwise, we add $x_{i}x_{i+1}$ to $F$. It’s easy to
check that, in every iteration of this procedure, only the vertices $u$ and
$v$ have the parity of their degree changed in $F$; the degree of every other
vertex stays the same (modulo 2). Since every connected component has an even
number of vertices, this means that, eventually, every vertex in $F$ will have
odd degree. ∎

Now it’s easy to check in logspace if every connected component of $G$ has an
even number of vertices using Reingold’s algorithm for undirected connectivity
[58]. It suffices to check if, for every vertex $v$ of $G$, the number of
vertices reachable from $v$ is odd. ∎

Now, if we only desire to obtain a function in $\mathsf{AC}^{0}$ not computed
by monotone circuits of depth $(\log n)^{i}$, we can follow the same argument
of Theorem 1.2, using Lemma 2.1 instead of Lemma 3.2. In order to obtain
moreover a monotone _graph property_ witnessing this separation, we will need
the following lemma, which enables us to obtain a graph property after
“padding” a graph property. We defer the proof of this lemma to the end of
this section.

######  Lemma 3.6.

Let $f:\left\\{0,1\right\\}^{\binom{n}{2}}\to\left\\{0,1\right\\}$ be a
monotone graph property on graphs of $n$ vertices. The following holds.

  1. 1.

If $f\in\mathsf{NC}^{i}$ for some $i>1$, then there exists a monotone graph
property $g$ on graphs of $N=2^{(\log n)^{i}}$ vertices such that
$g\in\mathsf{NC}^{1}$ and $f\leq^{\mathsf{mProj}}_{m}g$.

  2. 2.

If $f\in\mathsf{NL}$, then for all $\varepsilon>0$ there exists a monotone
graph property $g$ on graphs of $N=2^{n^{\varepsilon}}$ vertices such that $g$
can be computed by $\mathsf{AC}^{0}$ circuits of size $N^{2+o(1)}$ and
$f\leq^{\mathsf{mProj}}_{m}g$.

  3. 3.

If $f\in\oplus\mathsf{L}$, then for all $\varepsilon>0$ there exists a
monotone graph property $g$ on graphs of $N=2^{n^{\varepsilon}}$ vertices such
that $g$ can be computed by $\mathsf{AC}^{0}[\oplus]$ circuits of size
$N^{2+o(1)}$ and $f\leq^{\mathsf{mProj}}_{m}g$.

We are now ready to prove Theorem 3.3.

###### Proof of Theorem 3.3.

Fix $n\in{\mathbb{N}}$ and take an $\varepsilon<1/i$. Observing that
$\mathsf{L}\subseteq\mathsf{NL}$, from Theorem 3.5 and item (2) of Lemma 3.6
we conclude that there exists a monotone graph property $f$ on
$N=2^{n^{\varepsilon}}$ vertices such that $f\in\mathsf{AC}^{0}$ and
$\mathsf{OddFactor}_{n}\leq^{\mathsf{mProj}}_{m}f$. By Theorem 3.4, any
monotone circuit computing $f$ has depth $\Omega(n)=\Omega((\log
N)^{1/\varepsilon})\gg(\log N)^{i}$. ∎

Raz and Wigderson [66] observed that there exists a monotone function
$f\in\mathsf{NC}^{1}\setminus\mathsf{m}\mathsf{NC}$. Using Lemma 3.6, we
observe moreover that it’s possible to obtain this separation with a monotone
graph property.

######  Proposition 3.7.

We have
$\mathsf{NC}^{1}\cap\mathsf{Mono}\cap\mathsf{GraphProperties}\not\subseteq\mathsf{m}\mathsf{NC}$.

###### Proof.

Observing that $\mathsf{L}\subseteq\mathsf{NC}^{2}$, we conclude from Theorem
3.5 and item (1) of Lemma 3.6 that there exists a monotone graph property $f$
on $N=2^{(\log n)^{2}}$ vertices such that $f\in\mathsf{NC}^{1}$ and
$\mathsf{OddFactor}_{n}\leq^{\mathsf{mProj}}_{m}f$. By Theorem 3.4, any
monotone circuit computing $f$ has depth $\Omega(n)=\Omega(2^{\sqrt{\log
N}})$, which implies $f\not\in\mathsf{m}\mathsf{NC}$. ∎

###  3.3 Efficient monotone padding for graph properties

We will now prove Lemma 3.6. We first recall some low-depth circuits for
computing threshold functions, which we will use to design a circuit for
efficiently computing the adjacency matrix of induced subgraphs.

######  Theorem 3.8 ([36]).

Let $d>0$ be a constant. The function $\operatorname{THR}_{(\log n)^{d},n}$
can be computed by an $\mathsf{AC}^{0}$ circuit of size $n^{o(1)}$ and depth
$d+O(1)$.

######  Theorem 3.9 ([7]).

For every $k\in[n]$, the function $\operatorname{THR}_{k,n}$ can be computed
by a circuit of depth $O(\log n)$ and size $n^{O(1)}$.

######  Lemma 3.10.

There exists a circuit $C^{k}_{n}$ with $\binom{n}{2}+n$ inputs and
$\binom{k}{2}$ outputs which, when given as input an adjacency matrix of a
graph $G$ on $n$ vertices and a characteristic vector of a set $S\subseteq[n]$
such that $\lvert S\rvert\leq k$, outputs the adjacency matrix of the graph
$G[S]$, padded with isolated vertices when $\lvert S\rvert<k$. The circuit has
constant-depth and size $n^{2+o(1)}$ when $k=\operatorname{polylog}(n)$, and
size $n^{O(1)}$ and depth $O(\log n)$ otherwise.

###### Proof.

Let $\left\\{x_{ij}\right\\}_{i,j\in[n]}$ encode the adjacency matrix of $G$.
Let $\alpha\in\left\\{0,1\right\\}^{n}$ be the characteristic vector of $S$.
Let $i,j\in[k]$. Note that $\left\\{i,j\right\\}\in E(G[S])$ if and only if
there exists $a,b\in[n]$ such that

  * •

$\alpha_{a}$ is the $i$-th non-zero entry of $\alpha$,

  * •

$\alpha_{b}$ is the $j$-th non-zero entry of $\alpha$, and

  * •

$x_{ab}=1$ (i.e., $a$ and $b$ are connected in $G$).

We first consider the case $k=\operatorname{polylog}(n)$. In this case, the
first two conditions can be checked with circuits of size $n^{o(1)}$ using
Theorem 3.8. Therefore, we can compute if $i$ and $j$ are adjacent using
$n^{2+o(1)}$ gates and constant depth. As there are at most $(\log n)^{O(1)}$
such pairs, we can output $G[S]$ with at most $n^{2+o(1)}$ gates.

For any $k$, the first two conditions can be checked with an $\mathsf{NC}^{1}$
circuit by Theorem 3.9. Since there are at most $n^{2}$ pairs $i,j$, the
entire adjacency matrix can be computed with a $O(\log n)$-depth and
polynomial-size circuit. ∎

We are ready to prove Lemma 3.6.

###### Proof of Lemma 3.6.

We first prove (1). Fix $n\in{\mathbb{N}}$ and let $N=2^{(\log n)^{i}}$. For a
graph $G$ on $N$ vertices such that $\lvert E(G)\rvert\leq\binom{n}{2}$, let
${G}_{\mathsf{clean}}$ be the graph obtained from $G$ by removing isolated
vertices from $G$ one-by-one, in lexicographic order, until one of the
following two conditions are satisfied: (1) there are no more isolated
vertices in ${G}_{\mathsf{clean}}$, _or_ (2) ${G}_{\mathsf{clean}}$ has
exactly $n$ vertices. Let
$g:\left\\{0,1\right\\}^{\binom{N}{2}}\to\left\\{0,1\right\\}$ be the monotone
graph property defined as follows:

$\displaystyle g(G):=\left(\lvert
E(G)\rvert>\binom{n}{2}\right)\lor\left(\lvert
V({G}_{\mathsf{clean}})\rvert>n\right)\lor(f({G}_{\mathsf{clean}})=1).$

Note that $g$ accepts a graph $G$ if and only if at least one of the following
three conditions are satisfied:

  1. 1.

$G$ has at most $\binom{n}{2}$ edges, ${G}_{\mathsf{clean}}$ has exactly $n$
vertices and $f({G}_{\mathsf{clean}})=1$, or

  2. 2.

$G$ has more than $\binom{n}{2}$ edges, or

  3. 3.

${G}_{\mathsf{clean}}$ has more than $n$ vertices.

We observe that the monotonicity of $g$ follows from the monotonicity of $f$.
We also claim that $g$ is a graph property. Indeed, the graph
${G}_{\mathsf{clean}}$ is the same (up to isomorphism), irrespective of the
order according to which the isolated vertices are removed from $G$. Moreover,
the function $f$ is also a graph property. Because of this, all the three
conditions above are preserved under isomorphisms.

We first observe that $f$ is a monotone projection of $g$. Indeed, given a
graph $G$ on $n$ vertices, we can easily construct by a monotone projection a
graph $G^{\prime}$ on $N$ vertices and at most $\binom{n}{2}$ edges such that
$f(G)=g(G^{\prime})$. We just let $G^{\prime}$ have a planted copy of $G$, and
all other vertices are isolated. Then ${G^{\prime}}_{\mathsf{clean}}=G$ (up to
isomorphism) and $g(G^{\prime})=f({G}_{\mathsf{clean}})=f(G)$.

We now show how to compute $g$ in $\mathsf{NC}^{1}$. Let
$\left\\{x_{ij}\right\\}_{i,j\in[N]}$ be the input bits of $g$, corresponding
to the adjacency matrix of a graph $G$. The circuit computes as follows.

  1. 1.

If $\lvert E(G)\rvert>\binom{n}{2}$, accept the graph $G$.

  2. 2.

Compute the characteristic vector $\alpha\in\left\\{0,1\right\\}^{N}$ of the
set of all non-isolated vertices of $G$. If $\lvert\alpha\rvert_{1}>n$, accept
the graph $G$.

  3. 3.

Compute ${G}_{\mathsf{clean}}$ and output $f({G}_{\mathsf{clean}})$.

Note that checking if $\lvert E(G)\rvert>\binom{n}{2}$ can be done in
$\mathsf{NC}^{1}$ by Theorem 3.9. Moreover, for all $i\in[N]$, we have
$\alpha_{i}=\bigvee_{j\in[N]}x_{ij}$, and therefore $\alpha_{i}$ can be
computed by a circuit of depth $O(\log N)$ and $O(N)$ gates. In total, the
vector $\alpha$ can be computed with $O(N^{2})$ gates and $O(\log N)$ depth.
Finally, we can check if $\lvert\alpha\rvert_{1}>n$ in $\mathsf{NC}^{1}$ with
a threshold circuit.

For the final step, we compute ${G}_{\mathsf{clean}}$. If
$\lvert\alpha\rvert_{1}=n$, note that
${G}_{\mathsf{clean}}=G[\operatorname{supp}(\alpha)]$. When
$\lvert\alpha\rvert_{1}<n$, then ${G}_{\mathsf{clean}}$ is
$G[\operatorname{supp}(\alpha)]$ padded with isolated vertices. We can
therefore compute ${G}_{\mathsf{clean}}$ with the circuit $C_{N}^{n}$ of Lemma
3.10. Moreover, since $f\in\mathsf{NC}^{i}$, we have that $f$ can be computed
by a circuit of size $n^{O(1)}=N^{o(1)}$ and depth $O((\log n)^{i})=O(\log
N)$. Therefore, computing $f({G}_{\mathsf{clean}})$ can be done in
$\mathsf{NC}^{1}$. Overall, we get that $g\in\mathsf{NC}^{1}$.

In order to prove (2), it suffices to modify the proof above. The modification
can be briefly described as follows. We let $N=2^{n^{\varepsilon}}$. Every
time Lemma 3.10 is applied, we use the $\mathsf{AC}^{0}$ circuit instead of
the $\mathsf{NC}^{1}$ circuit, since $n=\operatorname{polylog}(N)$. This
ammounts to $N^{2+o(1)}$ many gates with unbounded fan-in. Moreover, since by
assumption $f\in\mathsf{NL}$, applying Lemma 2.1 we obtain an
$\mathsf{AC}^{0}$ circuit for $f$ of size $2^{n^{\varepsilon/2}}=N^{o(1)}$, so
we can compute $f({G}_{\mathsf{clean}})$ in constant depth with $N^{o(1)}$
gates.

Finally, for (3) it suffices to apply the same argument used for (2),
replacing an application of Lemma 2.1 by an application of Lemma 3.2. ∎

##  4 Non-Trivial Monotone Simulations and Their Consequences

In contrast to Section 3, in this section we observe that a non-trivial
simulation of $\mathsf{AC}^{0}$ circuits by monotone circuits is possible.
This follows from a refined version of the switching lemma proved by Rossman
[63]. As a proof of concept, we use this simulation result to reprove a well-
known $\mathsf{AC}^{0}$ lower bound for $\mathsf{Majority}$.

In the second part of this section, we show that if much faster simulations
are possible, then even stronger non-monotone circuit lower bounds follow. We
also show that this implication is true even if the simulation only holds for
_graph properties_. Monotone simulations for graph properties are motivated by
a result of Rossman [61], which shows that very strong monotone simulations
are possible for _homomorphism-preserving graph properties_. The lower bounds
from monotone simulations are proved with the simulation result and padding
argument used in the previous section (Lemmas 2.1 and 3.6).

###  4.1 A non-trivial simulation for bounded-depth circuits

The earliest monotone simulation result was proved for $\mathsf{DNF}$s by
Quine [55].

######  Theorem 4.1 (Quine [55]).

For all $s:{\mathbb{N}}\to{\mathbb{N}}$, we have
$\mathsf{DNF}[s]\cap\mathsf{Mono}\subseteq\mathsf{m}\mathsf{DNF}[s]$.

###### Proof.

If a given $\mathsf{DNF}$ computes a monotone Boolean function, simply
removing the negative literals continues to compute the same function. ∎

Let $\mathsf{DT}_{\mathsf{size}}(f)$ denote the size of a smallest decision-
tree computing $f$. We will need a result obtained by Rossman [63].

######  Theorem 4.2 ([63]).

If $f:\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ is computable by an
$\mathsf{AC}^{0}$ circuit of depth $d$ and size $s$, then
$\mathsf{DT}_{\mathsf{size}}(f)=2^{(1-{1/O(\log s)^{d-1}})n}$.

######  Theorem 4.3.

Let $s:{\mathbb{N}}\to{\mathbb{N}}$ and $d\geq 1$. We have
$\mathsf{AC}^{0}_{d}[s]\cap\mathsf{Mono}\subseteq\mathsf{m}\mathsf{SIZE}[t]$,
where $t=n\cdot 2^{n(1-{1/O(\log s)^{d-1}})}$. Moreover, this upper bound is
achieved by monotone $\mathsf{DNFs}$ of size $t/n$.

###### Proof.

Let $f$ be a monotone function computable by an $\mathsf{AC}^{0}$ circuit of
depth $d$ and size $s$. By Theorem 4.2, there exists a decision tree of size
$2^{(1-{1/O(\log s)^{d-1}})n}$ computing $f$. Therefore, there exists a
$\mathsf{DNF}$ of the same size computing $f$, which can be taken to be
monotone by by Theorem 4.1. This can be converted into a monotone circuit of
size $n\cdot 2^{(1-{1/O(\log s)^{d-1}})n}$. ∎

We observe that it is possible to immediately deduce an $\mathsf{AC}^{0}$
lower bound for $\mathsf{Majority}$ using this simulation theorem. Even though
near-optimal lower bounds for $\mathsf{Majority}$ have been known for a long
time [34] and the proof of the main technical tool (Theorem 4.2) behind our
simulation result is similar to the one used by [34], the argument below
illustrates how a monotone simulation can lead to non-monotone circuit lower
bounds.

######  Corollary 4.4.

Any depth-$d$ $\mathsf{AC}^{0}$ circuit computing $\mathsf{Majority}$ has size
$2^{\Omega((n/\log n)^{1/(d-1)})}$.

###### Proof.

Note that $\mathsf{Majority}$ has $\binom{n}{n/2}=\Omega(2^{n}/\sqrt{n})$
minterms. Therefore, any monotone $\mathsf{DNF}$ computing $\mathsf{Majority}$
has size at least $\Omega(2^{n}/\sqrt{n})$. By Theorem 4.3, it follows that
the size $s$ of a depth-$d$ $\mathsf{AC}^{0}$ computing $\mathsf{Majority}$
satisfies the following inequality:

$2^{n(1-{1/O(\log s)^{d-1}})}=\Omega(2^{n-\frac{1}{2}\log n}).$

From this equation we obtain $s=2^{\Omega((n/\log n)^{1/(d-1)})}$. ∎

###  4.2 Non-monotone lower bounds from monotone simulations

We now show that if monotone circuits are able to efficiently simulate non-
monotone circuits computing monotone Boolean functions, then striking
complexity separations follow. We also show a result of this kind for
simulations of graph properties. We first prove a lemma connecting the
simulation of $\mathsf{AC}^{0}$ circuits with the simulation of $\mathsf{NL}$
machines.

######  Lemma 4.5.

For all constants $\varepsilon>0$ and $C\geq 1$, if
$\mathsf{AC}^{0}\cap\mathsf{Mono}\subseteq\mathsf{m}\mathsf{SIZE}[2^{O((\log
n)^{C})}]$, then
$\mathsf{NL}\cap\mathsf{Mono}\subseteq\mathsf{m}\mathsf{SIZE}[2^{o(n^{\varepsilon})}]$.

###### Proof.

We prove the contrapositive. Suppose that there exists $\varepsilon>0$ such
that
$\mathsf{NL}\cap\mathsf{Mono}\not\subseteq\mathsf{m}\mathsf{SIZE}[2^{o(n^{\varepsilon})}]$.
This means that there exists a monotone function $f$ such that
$f\in\mathsf{NL}$ and any monotone circuit computing $f$ has size
$2^{\Omega(n^{\varepsilon})}$.

Let $\delta=\varepsilon/(2C)$ and let $m=2^{n^{\delta}}$. Let
$g:\left\\{0,1\right\\}^{n}\times\left\\{0,1\right\\}^{m}\to\left\\{0,1\right\\}$
be the Boolean function defined as $g(x,y)=f(x)$. Note that $g$ is a function
on $N:=m+n=2^{\Theta(n^{\delta})}$ bits. By Lemma 2.1, there exists an
$\mathsf{AC}^{0}$ circuit computing $f$ of size $2^{n^{\delta}}=N^{O(1)}$.
Moreover, any monotone circuit computing $g$ has size
$2^{\Omega(n^{\varepsilon})}=2^{\Omega((\log
N)^{\varepsilon/\delta})}=2^{\Omega((\log N)^{2C})}$. ∎

Next, we recall the strongest known monotone circuit and formula lower bounds
for a monotone function in $\mathsf{NP}$.

######  Theorem 4.6 ([53]).

$\mathsf{NP}\cap\mathsf{Mono}\not\subseteq\mathsf{m}\mathsf{DEPTH}[o(n)]$.

######  Theorem 4.7 ([22]).

$\mathsf{NP}\cap\mathsf{Mono}\not\subseteq\mathsf{m}\mathsf{SIZE}[2^{o(\sqrt{n}/\log
n)}]$.

We are now ready to state and prove our first result regarding new complexity
separations from monotone simulations. Recall that obtaining explicit lower
bounds against depth-$3$ $\mathsf{AC}^{0}$ circuits of size
$2^{\omega(n^{1/2})}$ is a major challenge in circuit complexity theory, while
the best lower bound on the size of depth-4 $\mathsf{AC}^{0}$ circuits
computing a function in $\mathsf{NP}$ is currently $2^{\Omega(n^{1/3})}$ [34].
Moreover, no strict separation is known in the following sequence of
inclusions of complexity classes:
$\mathsf{ACC}\subseteq\mathsf{TC}^{0}\subseteq\mathsf{NC}^{1}\subseteq\mathsf{L}\subseteq\mathsf{NL}\subseteq\oplus\mathsf{L}\subseteq\mathsf{NC}^{2}$.
We show that efficient monotone simulations would bring new results in both of
these fronts. (We stress that all lower bound consequences appearing below
refer to separations against non-uniform circuits.)161616In other words, all
upper bounds are _uniform_ , but the lower bounds hold even for _non-uniform_
circuits. Note that this is stronger than lower bounds for uniform circuits.

######  Theorem 4.8.

Let ${\mathcal{C}}$ be a class of circuits. There exists $\varepsilon>0$ such
that the following holds:

  1. 1.

If $\mathsf{AC}^{0}_{3}\cap\mathsf{Mono}\subseteq\mathsf{m}\mathsf{NC}^{1}$,
then $\mathsf{NP}\not\subseteq\mathsf{AC}^{0}_{3}[2^{o(n)}]$.

  2. 2.

If
$\mathsf{AC}^{0}_{4}\cap\mathsf{Mono}\subseteq\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$,
then $\mathsf{NP}\not\subseteq\mathsf{AC}^{0}_{4}[2^{o(\sqrt{n}/\log n)}]$.

  3. 3.

If
${\mathcal{C}}\cap\mathsf{Mono}\subseteq\mathsf{m}\mathsf{SIZE}[2^{O(n^{\varepsilon})}]$,
then $\mathsf{NC}^{2}\not\subseteq{\mathcal{C}}$.

  4. 4.

If
$\mathsf{AC}^{0}\cap\mathsf{Mono}\subseteq\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$,
then $\mathsf{NC}^{2}\not\subseteq\mathsf{NC}^{1}$.

###### Proof.

We will prove each item separately.

  1. _Proof of (1)_.

Let us assume that
$\mathsf{AC}^{0}_{3}\cap\mathsf{Mono}\subseteq\mathsf{m}\mathsf{NC}^{1}$. Let
$f$ be the function of Theorem 4.6. For a contradiction, suppose that
$f\in\mathsf{AC}^{0}_{3}[2^{o(n)}]$. Let $\alpha:{\mathbb{N}}\to{\mathbb{N}}$
be such that $\alpha(n)\to_{n}\infty$ and $f$ has a depth-3 $\mathsf{AC}^{0}$
circuit of size $2^{n/\alpha}$. Let $m=2^{n/(10\cdot\alpha)}$ and let
$g:\left\\{0,1\right\\}^{n}\times\left\\{0,1\right\\}^{m}\to\left\\{0,1\right\\}$
be the function $g(x,y)=f(x)$. Let $N=n+m=(1+o(1))2^{n/(10\cdot\alpha)}$.
Clearly, the function $g$ has a depth-3 $\mathsf{AC}^{0}$ circuit of size
$2^{n/\alpha}=N^{O(1)}$. Since $g$ is monotone, we conclude from the
assumption that $g$ is computed by a polynomial-size monotone formula. Now,
since $f(x)=g(x,1^{m})$, we obtain a monotone formula of size
$N^{O(1)}=2^{o(n)}$ for computing $f$, which contradicts the lower bound of
Theorem 4.6.

  2. _Proof of (2)_.

Similar to the proof of item (1), but using Theorem 4.7 instead.

  3. _Proof of (3)_.

Suppose that $\mathsf{NC}^{2}\subseteq{\mathcal{C}}$. By Theorem 3.1, there
exists a monotone function $f\in\mathsf{NC}^{2}$ on $n$ bits and a number
$\varepsilon>0$ such that
$f\notin\mathsf{m}\mathsf{SIZE}[2^{o(n^{\varepsilon})}]$. Therefore, for any
$\delta>0$ such that $\delta<\varepsilon$, we have
$f\notin\mathsf{m}\mathsf{SIZE}[2^{O(n^{\delta})}]$. Since, by assumption, we
have $f\in\mathsf{NC}^{2}\subseteq{\mathcal{C}}$, we obtain
${\mathcal{C}}\cap\mathsf{Mono}\not\subseteq\mathsf{m}\mathsf{SIZE}[2^{O(n^{\delta})}]$.

  4. _Proof of (4)_.

If $\mathsf{NC}^{2}\subseteq\mathsf{NC}^{1}$, then, by item (3), we get
$\mathsf{NC}^{1}\cap\mathsf{Mono}\not\subseteq\mathsf{m}\mathsf{SIZE}[2^{o(n^{\varepsilon})}]$.
From Lemma 4.5, we obtain
$\mathsf{AC}^{0}\cap\mathsf{Mono}\not\subseteq\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$.
∎

As a motivation to the ensuing discussion, we recall a result of Rossman [61],
who showed that any homomorphism-preserving graph property computed by
$\mathsf{AC}^{0}$ circuits is also computed by monotone $\mathsf{AC}^{0}$
circuits.

######  Theorem 4.9 ([61]).

$\mathsf{AC}^{0}\cap\mathsf{HomPreserving}\subseteq\mathsf{m}\mathsf{DNF}[\mathsf{poly}]$.

This inspires the question of whether general graph properties can also be
efficiently simulated by monotone circuits. We show that, if true, such
simulations would imply strong complexity separations. Let us first recall an
exponential monotone circuit lower bound for monotone graph properties, and we
will be ready to state and prove our main result.

######  Theorem 4.10 ([1]).

There exists $\varepsilon>0$ such that
$\mathsf{NP}\cap\mathsf{Mono}\cap\mathsf{GraphProperties}\not\subseteq\mathsf{m}\mathsf{SIZE}[2^{o(n^{\varepsilon})}]$.

######  Theorem 4.11.

Let ${\mathcal{C}}$ be a class of circuits. The following holds:

  1. 1.

If
${\mathcal{C}}\cap\mathsf{Mono}\cap\mathsf{GraphProperties}\subseteq\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$,
then $\mathsf{L}\not\subseteq{\mathcal{C}}$.

  2. 2.

If
${\mathcal{C}}\cap\mathsf{Mono}\cap\mathsf{GraphProperties}\subseteq\mathsf{m}\mathsf{DEPTH}[o(\sqrt{n})]$,
where $n$ denotes the number of input bits, then
$\mathsf{L}\not\subseteq{\mathcal{C}}$.

  3. 3.

If
$\mathsf{AC}^{0}\cap\mathsf{Mono}\cap\mathsf{GraphProperties}\subseteq\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$,
then $\mathsf{NP}\not\subseteq\mathsf{NC}^{1}$.

###### Proof.

We will prove each item separately.

  1. _Proof of (1)_.

Suppose that $\mathsf{L}\subseteq{\mathcal{C}}$. By Theorem 3.4, the monotone
graph property $\mathsf{OddFactor}$ satisfies
$\mathsf{OddFactor}\notin\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$. Moreover, we
have the upper bound $\mathsf{OddFactor}\in\mathsf{L}$ by Theorem 3.5. Since,
by assumption, we have
$\mathsf{OddFactor}\in\mathsf{L}\subseteq{\mathcal{C}}$, we obtain
${\mathcal{C}}\cap\mathsf{Mono}\cap\mathsf{GraphProperties}\not\subseteq\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$.

  2. _Proof of (2)_.

Suppose that $\mathsf{L}\subseteq{\mathcal{C}}$. By Theorems 3.5 and 3.4,
there exists a monotone graph property $f\in\mathsf{L}$ such that
$f\notin\mathsf{m}\mathsf{DEPTH}[o(\sqrt{n})]$. Since, by assumption, we have
$f\in\mathsf{L}\subseteq{\mathcal{C}}$, we obtain
${\mathcal{C}}\cap\mathsf{Mono}\cap\mathsf{GraphProperties}\not\subseteq\mathsf{m}\mathsf{DEPTH}[o(\sqrt{n})]$.

  3. _Proof of (3)_.

Suppose that $\mathsf{NP}\subseteq\mathsf{NC}^{1}$. By Theorem 4.10, there
exists a monotone graph property $f\in\mathsf{NC}^{1}$ such that
$\mathsf{mSIZE}({f})=2^{\Omega(n^{\varepsilon})}$ for some $\varepsilon>0$.
Let $\delta=\varepsilon/2$. By Lemma 3.6 (Item $2$), there exists a monotone
graph property $g$ on $N=2^{n^{\delta}}$ vertices computed by an
$\mathsf{AC}^{0}$ circuit of size $N^{2+o(1)}$ such that $f$ is a monotone
projection of $g$. Theorem 4.10 implies that any monotone circuit computing
$f$ has size $2^{\Omega(n^{\varepsilon})}=2^{\Omega((\log
N)^{2})}=N^{\omega(1)}$. ∎

##  5 Monotone Complexity of Constraint Satisfaction Problems

In this section, we study the monotone complexity of Boolean-valued
$\mathsf{CSP}$s. Our goal is to classify which types of Boolean
$\mathsf{CSP}$s are hard for monotone circuit size and monotone circuit depth,
eventually proving Theorems 1.4 and 1.5.

We will first spend some time recalling standard definitions and concepts in
the theory of CSPs (Section 5.1), as well as a few results about CSPs that
were proved in previous works [67, 39, 9, 10, 2] (Section 5.2). We will then
prove Theorem 1.5 in Section 5.3, and we will finally prove Theorem 1.4 in
Section 5.5 after proving some auxiliary results in Section 5.4.

###  5.1 Definitions

For a good introduction to the concepts defined below, we refer the reader to
[9, 10]. We also refer the reader to Section 1.1.3 for the definition of the
family of functions $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$, as well as the
terms _constraint application, $S$-formula_ and _satisfiable formula_.

We denote by $p_{i}^{n}:\left\\{0,1\right\\}^{n}\to\left\\{0,1\right\\}$ the
$i$-th _projection function_ on $n$ variables, whose operation is defined as
$p_{i}^{n}(x)=x_{i}$. For a set of Boolean functions $B$, we denote by $[B]$
the _closure_ of $B$, defined as follows: a Boolean function $f$ is in $[B]$
if and only if $f\in B\cup\left\\{\mathrm{Identity}\right\\}$ or if there
exists $g\in B$ and $h_{1},\dots,h_{k}$ such that $f=g(h_{1},\dots,h_{k})$,
where each $h_{i}$ is either a projection function or a function from $[B]$.
We can equivalently define $[B]$ as the set of all Boolean functions that can
be computed by circuits using the functions of $B$ as gates. Note that $[B]$
necessarily contains an infinite number of Boolean functions, since
$p_{1}^{n}\in[B]$ for every $n\in{\mathbb{N}}$; moreover, the constant
functions are not necessarily in $[B]$. We say that $B$ is a _clone_ if
$B=[B]$. A few prominent examples of clones are the set of all Boolean
functions (equal to $[\left\\{\land,\neg\right\\}]$), monotone functions
(equal to $[\left\\{\land,\lor,0,1\right\\}]$), and linear functions (equal to
$[\left\\{\oplus,1\right\\}]$).

######  Remark 5.1.

The set of all clones forms a lattice, known as _Post’s lattice_ , under the
operations $[A]\sqcap[B]:=[A]\cap[B]$ and $[A]\sqcup[B]:=[A\cup B]$. From the
next section onwards, we will refer to the clones defined in [9] (such as
$\mathrm{I_{0}}$, $\mathrm{I_{1}}$, etc.), assuming the reader is familiar
with them. For the unfamiliar reader, we refer to Appendix C and Figures 4 and
1, which contain all the definitions of the clones we will need, as well as
the entire Post’s lattice in graphical representation.

To avoid confusion, we will always refer to clones with
$\mathrm{normal}$-$\mathrm{Roman}$ font (e.g.,
$\mathrm{S_{1}},\mathrm{I_{0}}$, etc).

Let $S$ be a finite set of Boolean relations. We denote by $\mathsf{CNF}(S)$
the set of all $S$-formulas. We denote by $\mathsf{COQ}(S)$ the set of all
relations which can be expressed with the following type of formula $\varphi$:

$\varphi(x_{1},\dots,x_{k})=\exists
y_{1},\dots,y_{\ell}\,\psi(x_{1},\dots,x_{k},y_{1},\dots,y_{\ell}),$

where $\psi\in\mathsf{CNF}(S)$. The relations in $\mathsf{COQ}(S)$ will also
be referred as _conjunctive queries_ over $S$. We denote by $\left\langle
S\right\rangle$ the set of relations defined as $\left\langle
S\right\rangle:=\mathsf{COQ}(S\cup\left\\{=\right\\})$. If $S=\left\langle
S\right\rangle$, we say that $S$ is a _co-clone_. We define

$\mathsf{CSP}=\left\\{\mathsf{CSP}\text{-}\mathsf{SAT}_{S}:\text{$S$ is a
finite set of relations}\right\\}.$

We say that $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is _trivial_ if
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is a constant function.

Let $R$ be a $k$-ary Boolean relation and let
$f:\left\\{0,1\right\\}^{\ell}\to\left\\{0,1\right\\}$ be a Boolean function.
For $x\in R$ and $i\in[k]$, we denote by $x[i]$ the $i$-th bit of $x$.

######  Definition 5.2.

We say that $f$ is a _polymorphism_ of $R$, and $R$ is _an invariant of $f$_,
if, for all $x_{1},\dots,x_{\ell}\in R$, we have

$(f(x_{1}[1],\dots,x_{\ell}[1]),f(x_{2}[2],\dots,x_{\ell}[2]),\dots,f(x_{k}[k],\dots,x_{\ell}[k]))\in
R.$

We denote the set of all polymorphisms of $R$ by $\mathsf{Pol}(R)$. For a set
of relations $S$, we denote by $\mathsf{Pol}(S)$ the set of Boolean functions
which are polymorphisms of all the relations of $S$. For a set of Boolean
functions, we denote by $\mathsf{Inv}(B)$ the set of all Boolean relations
which are invariant under all functions of $B$ (i.e.,
$\mathsf{Inv}(B)=\left\\{R:B\subseteq\mathsf{Pol}(R)\right\\}$).

The following summarises the important facts about clones, co-clones and
polymorphisms that are relevant to the study of CSPs [38].

######  Lemma 5.3.

Let $S$ and $S^{\prime}$ be sets of Boolean relations and let $B$ and
$B^{\prime}$ be sets of Boolean functions. We have

  1. (i)

$\mathsf{Pol}(S)$ is a clone and $\mathsf{Inv}(B)$ is a co-clone;

  2. (ii)

If $S\subseteq S^{\prime}$, then
$\mathsf{Pol}(S^{\prime})\subseteq\mathsf{Pol}(S)$;

  3. (iii)

If $B\subseteq B^{\prime}$, then
$\mathsf{Inv}(B^{\prime})\subseteq\mathsf{Inv}(B)$;

  4. (iv)

$\mathsf{COQ}(\mathsf{COQ}(S))=\mathsf{COQ}(S)$;

  5. (v)

If $S\subseteq S^{\prime}$, then
$\mathsf{COQ}(S)\subseteq\mathsf{COQ}(S^{\prime})$;

  6. (vi)

$\mathsf{Inv}(\mathsf{Pol}(S))=\left\langle S\right\rangle$;

  7. (vii)

$\mathsf{Pol}(\mathsf{Inv}(B))=[B]$.

We now define different types of reductions. We say that a reduction is a
_monotone OR-reduction_ if every bit of the reduction is either constant or
can be computed by a monotone disjunction on the input variables. We write
$f\leq^{\mathsf{mOR}}_{m}g$ if there exists a many-one monotone OR-reduction
from $f$ to $g$. We also write $f\leq^{\mathsf{AC}^{0}}_{m}\\!g$ if there
exists a many-one $\mathsf{AC}^{0}$ reduction from $f$ to $g$, and
$f\leq^{\mathsf{m}\mathsf{NL}}_{m}g$ if there exists a many-one
$\mathsf{m}\mathsf{NL}$ reduction from $f$ to $g$171717A many-one
$\mathsf{AC}^{0}$ (resp. $\mathsf{m}\mathsf{NL}$) reduction is one in which
each bit of the reduction is either constant or can be computed with a
polynomial-size $\mathsf{AC}^{0}$ circuit (resp. monotone nondeterministic
branching program). Recall that a _monotone nondeterministic branching
program_ is a directed acyclic graph $G$ with two distinguished vertices $s$
and $t$, in which each edge $e$ is labelled with an input function
$\rho_{e}\in\left\\{1,x_{1},\dots,x_{n}\right\\}$. Given an input $x$, the
program accepts if there exists a path from $s$ to $t$ in the subgraph $G_{x}$
of $G$ in which an edge $e$ appears if $\rho_{e}(x)=1$. . Unless otherwise
specified, every reduction we consider will generate an instance of polynomial
size on the length of the input.

Finally, we denote by $\mathsf{OR}^{k}$ and $\mathsf{NAND}^{k}$ the $k$-ary
$\mathsf{OR}$ and $\mathsf{NAND}$ relations, respectively.

###  5.2 Basic facts about $\mathsf{CSP}\text{-}\mathsf{SAT}$

We state here basic facts about the $\mathsf{CSP}\text{-}\mathsf{SAT}$
function. These facts are proved in the original paper of Schaefer [67], as
well as in later papers [39, 9, 10, 2].

Lemma 5.4 below is one of the most important lemmas of this section and will
be used many times. It states that $\mathsf{Pol}(S)$ characterises the
monotone complexity of $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$, in the sense
that the sets of relations with few polymorphisms give rise to the hardest
instances of CSPs. A non-monotone version of this result was proved in [39,
10, Theorem 2.4], and we check in Section B.2 that their proofs also hold in
the monotone case.

######  Lemma 5.4 (Polymorphisms characterise the complexity of CSPs [39, 10,
Theorem 2.4]).

If $\mathsf{Pol}(S_{2})\subseteq\mathsf{Pol}(S_{1})$, then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S_{1}}^{n}\leq^{\mathsf{m}\mathsf{NL}}_{m}\mathsf{CSP}\text{-}\mathsf{SAT}_{S_{2}}^{\mathsf{poly}(n)}$.

Theorem 5.5 gives monotone circuit upper bounds for some instances of
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$. Non-monotone variants of this upper
bound were originally obtained in the seminal paper of Schaefer [67], and we
again check that the monotone variants work in Section B.3.

######  Theorem 5.5 (Monotone version of the upper bounds for
$\mathsf{CSP}\text{-}\mathsf{SAT}$ [67, 2]).

Let $S$ be a finite set of relations. The following holds.

  1. 1.

If $\mathrm{\mathrm{E_{2}}}\subseteq\mathsf{Pol}(S)$ or
$\mathrm{\mathrm{V_{2}}}\subseteq\mathsf{Pol}(S)$, then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\in\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$.

  2. 2.

If $\mathrm{\mathrm{D_{2}}}\subseteq\mathsf{Pol}(S)$, or
$\mathrm{\mathrm{S_{00}}}\subseteq\mathsf{Pol}(S)$, or
$\mathrm{\mathrm{S_{10}}}\subseteq\mathsf{Pol}(S)$, then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\in\mathsf{m}\mathsf{NL}$.

Finally, we state here a result of [2], which classifies the _non-monotone_
complexity of $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ under
$\leq^{\mathsf{AC}^{0}}_{m}\\!$ reductions. The classification of the
complexity of $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is based solely on
$\mathsf{Pol}(S)$. See Figure 1 for a graphical representation.

######  Theorem 5.6 (Refined classification of $\mathsf{CSP}$ problems [2,
Theorem 3.1]).

Let $S$ be a finite set of Boolean relations. The following holds.

  * •

If $\mathrm{I_{0}}\subseteq\mathsf{Pol}(S)$ or
$\mathrm{I_{1}}\subseteq\mathsf{Pol}(S)$, then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is trivial.

  * •

If $\mathsf{Pol}(S)\in\left\\{\mathrm{I_{2}},\mathrm{N_{2}}\right\\}$, then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is
$\leq^{\mathsf{AC}^{0}}_{m}\\!$-complete for $\mathsf{NP}$.

  * •

If $\mathsf{Pol}(S)\in\left\\{\mathrm{V_{2}},\mathrm{E_{2}}\right\\}$, then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is
$\leq^{\mathsf{AC}^{0}}_{m}\\!$-complete for $\mathsf{P}$.

  * •

If $\mathsf{Pol}(S)\in\left\\{\mathrm{L_{2}},\mathrm{L_{3}}\right\\}$, then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is
$\leq^{\mathsf{AC}^{0}}_{m}\\!$-complete for $\oplus\mathsf{L}$.

  * •

If $\mathrm{S_{00}}\subseteq\mathsf{Pol}(S)\subseteq\mathrm{S_{00}}^{2}$ or
$\mathrm{S_{10}}\subseteq\mathsf{Pol}(S)\subseteq\mathrm{S_{10}}^{2}$ or
$\mathsf{Pol}(S)\in\left\\{\mathrm{D_{2}},\mathrm{M_{2}}\right\\}$, then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is
$\leq^{\mathsf{AC}^{0}}_{m}\\!$-complete for $\mathsf{NL}$.

  * •

If $\mathsf{Pol}(S)\in\left\\{\mathrm{D_{1}},\mathrm{D}\right\\}$, then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is
$\leq^{\mathsf{AC}^{0}}_{m}\\!$-complete for $\mathsf{L}$.

  * •

If $\mathrm{S_{02}}\subseteq\mathsf{Pol}(S)\subseteq\mathrm{R_{2}}$ or
$\mathrm{S_{12}}\subseteq\mathsf{Pol}(S)\subseteq\mathrm{R_{2}}$, then either
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\in\mathsf{AC}^{0}$ or
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is
$\leq^{\mathsf{AC}^{0}}_{m}\\!$-complete for $\mathsf{L}$.

$\mathrm{I}$$\mathrm{I_{0}}$$\mathrm{I_{1}}$$\mathrm{I_{2}}$$\mathrm{N_{2}}$$\mathrm{N}$$\mathrm{V}$$\mathrm{V_{0}}$$\mathrm{V_{1}}$$\mathrm{V_{2}}$$\mathrm{L}$$\mathrm{L_{0}}$$\mathrm{L_{1}}$$\mathrm{L_{2}}$$\mathrm{L_{3}}$$\mathrm{E}$$\mathrm{E_{0}}$$\mathrm{E_{1}}$$\mathrm{E_{2}}$$\mathrm{D_{2}}$$\mathrm{S_{0}}$$\mathrm{S_{00}}$$\mathrm{S_{01}}$$\mathrm{S_{02}}$$\mathrm{S_{1}}$$\mathrm{S_{10}}$$\mathrm{S_{11}}$$\mathrm{S_{12}}$$\mathrm{D_{1}}$$\mathrm{D}$$\mathrm{S^{3}_{0}}$$\mathrm{S^{3}_{00}}$$\mathrm{S^{3}_{01}}$$\mathrm{S^{3}_{02}}$$\mathrm{S^{3}_{1}}$$\mathrm{S^{3}_{10}}$$\mathrm{S^{3}_{11}}$$\mathrm{S^{3}_{12}}$$\mathrm{S^{2}_{0}}$$\mathrm{S^{2}_{00}}$$\mathrm{S^{2}_{01}}$$\mathrm{S^{2}_{02}}$$\mathrm{S^{2}_{1}}$$\mathrm{S^{2}_{10}}$$\mathrm{S^{2}_{11}}$$\mathrm{S^{2}_{12}}$$\mathrm{M}$$\mathrm{M_{0}}$$\mathrm{M_{1}}$$\mathrm{M_{2}}$$\mathrm{BF}$$\mathrm{R_{0}}$$\mathrm{R_{1}}$$\mathrm{R_{2}}$

$\mathsf{NP}$-complete |  $\mathsf{P}$-complete |  $\oplus\mathsf{L}$-complete
---|---|---
$\mathsf{NL}$-complete |  $\mathsf{L}$-complete |  $\mathsf{L}$-complete or in $\mathsf{coNLOGTIME}$
|  Trivial |

Figure 1:  Graph of all closed classes of Boolean functions. The vertices are
colored with the complexity of deciding $\mathsf{CSP}$s whose set of
polymorphisms corresponds to the label of the vertex. Trivial $\mathsf{CSP}$s
are those that correspond to constant functions. Every hardness result is
proved under $\leq^{\mathsf{AC}^{0}}_{m}\\!$ reductions. See Theorem 5.6 for
details. A similar figure appears in [2, Figure 1].

###  5.3 A monotone dichotomy for $\mathsf{CSP}\text{-}\mathsf{SAT}$

In this section, we prove Theorem 1.5. We first prove Part (1) of the theorem
(the dichotomy for circuit size), and then we prove Part (2) of the theorem
(the dichotomy for circuit depth).

###### Dichotomy for circuits.

To prove the dichotomy for circuits, we first show that, for any set of
relations $S$ whose set of polymorphisms is contained in $\mathrm{L_{3}}$, we
can monotonically reduce $\mathsf{3\mbox{-}XOR\mbox{-}SAT}$ to
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$.

######  Lemma 5.7.

Let $S$ be a finite set of relations. If
$\mathsf{Pol}(S)\subseteq\mathrm{L_{3}}$, then
$\mathsf{3\mbox{-}XOR\mbox{-}SAT}\leq^{\mathsf{m}\mathsf{NL}}_{m}\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$.

###### Proof.

Inspecting Post’s lattice (Figure 1), note that the only clones strictly
contained in $\mathrm{L_{3}}$ are $\mathrm{L_{2}},\mathrm{N_{2}}$ and
$\mathrm{I_{2}}$. We will first show that the reduction holds for the case
$\mathsf{Pol}(S)=\mathrm{L_{2}}$ and then prove that the reduction also holds
for the case $\mathsf{Pol}(S)=\mathrm{L_{3}}$. Lemma 5.4 will then imply the
cases $\mathsf{Pol}(S)\in\left\\{\mathrm{N_{2}},\mathrm{I_{2}}\right\\}$,
since $\mathrm{I_{2}}\subseteq\mathrm{N_{2}}\subseteq\mathrm{L_{3}}$.

It’s not hard to check that, if $\mathsf{Pol}(S)=\mathrm{L_{2}}$, then
$\mathsf{Pol}(S)\subseteq\mathsf{Pol}(\mathsf{3\mbox{-}XOR\mbox{-}SAT})$ (it
suffices to observe that bitwise XORing three satisfying assignments to a
linear equation gives rise to a new satisfying assignment to the same
equation). Therefore, from Lemma 5.4 we deduce that
$\mathsf{3\mbox{-}XOR\mbox{-}SAT}$ admits a reduction to
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ in $\mathsf{m}\mathsf{NL}$. In order to
prove the case $\mathsf{Pol}(S)=\mathrm{L_{3}}$, we first prove the following
claim.

######  Claim ([2, Lemma 3.11]).

Let $S$ be a finite set of relations such that
$\mathsf{Pol}(S)=\mathrm{L_{2}}$. There exists a finite set of relations
$S^{\prime}$ such that $\mathsf{Pol}(S^{\prime})=\mathrm{L_{3}}$ and
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}^{n}\leq^{\mathsf{mProj}}_{m}\mathsf{CSP}\text{-}\mathsf{SAT}_{S^{\prime}}^{n+1}$.

###### Proof.

We describe the proof of Lemma 3.11 in [2] and observe that it gives a
monotone reduction.

For a relation $R\in S$, let $R^{\prime}=\left\\{(\neg x_{1},\dots,\neg
x_{k}):(x_{1},\dots,x_{k})\in R\right\\}$. Let also
$S^{\prime}=\left\\{R^{\prime}:R\in S\right\\}$. It’s not hard to check that
$\mathsf{Pol}(S^{\prime})=\mathrm{L_{3}}$, since $S^{\prime}$ is an invariant
of $\mathrm{L_{2}}$ and $\mathrm{N_{2}}$, and $\mathrm{L_{3}}$ is the smallest
clone containing both $\mathrm{L_{2}}$ and $\mathrm{N_{2}}$; moreover, if
$\rho\in\mathsf{Pol}(S^{\prime})$ and $\rho$ is a Boolean function on at least
two bits, then $\rho\in\mathsf{Pol}(S)=\mathrm{L_{2}}$.

Now let $F$ be a instance of $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}^{n}$. For
every constraint $C=R(x_{1},\dots,x_{k})$ in $F$, we add the constraint
$C^{\prime}=R^{\prime}(\alpha,x_{1},\dots,x_{k})$ to the $S^{\prime}$-formula
$F^{\prime}$, where $\alpha$ is a new variable. Note that $F^{\prime}$ is a
$S^{\prime}$-formula, defined on $n+1$ variables, which is satisfiable if and
only if $F$ is satisfiable. Moreover, the construction of $F^{\prime}$ from
$F$ can be done with a monotone projection. ∎

Since the case $\mathsf{Pol}(S)=\mathrm{L_{2}}$ holds, the case
$\mathsf{Pol}(S)=\mathrm{L_{3}}$ now follows from Lemma 5.4 and the Claim.
Finally, from Lemma 5.4 we conclude that the reduction also holds for the case
$\mathsf{Pol}(S)\in\left\\{\mathrm{N_{2}},\mathrm{I_{2}}\right\\}$, since
$\mathrm{I_{2}}\subseteq\mathrm{N_{2}}\subseteq\mathrm{L_{3}}$. ∎

######  Theorem 5.8 (Dichotomy for monotone circuits).

Let $S$ be a finite set of relations. If
$\mathsf{Pol}(S)\subseteq\mathrm{L_{3}}$ then there exists a constant
$\varepsilon>0$ such that
$\mathsf{mSIZE}({\mathsf{CSP}\text{-}\mathsf{SAT}_{S}})=2^{\Omega(n^{\varepsilon})}$.
Otherwise, we have
$\mathsf{mSIZE}({\mathsf{CSP}\text{-}\mathsf{SAT}_{S}})=n^{O(1)}$.

###### Proof.

If $\mathsf{Pol}(S)\subseteq\mathrm{L_{3}}$, the lower bound follows from the
’moreover’ part of Theorem 3.1, and Lemma 5.7. For the upper bound, we inspect
Post’s lattice (Figure 1). Observe that, if
$\mathsf{Pol}(S)\not\subseteq\mathrm{L_{3}}$, the following are the only
possible cases:

  1. 1.

$\mathrm{I_{0}}\subseteq\mathsf{Pol}(S)$ or
$\mathrm{I_{1}}\subseteq\mathsf{Pol}(S)$. In both cases, any $\mathsf{CNF}(S)$
is trivially satisfiable.

  2. 2.

$\mathrm{E_{2}}\subseteq\mathsf{Pol}(S)$ or
$\mathrm{V_{2}}\subseteq\mathsf{Pol}(S)$. In this case,
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\in\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$
by Theorem 5.5.

  3. 3.

$\mathrm{D_{2}}\subseteq\mathsf{Pol}(S)$. In this case,
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\in\mathsf{m}\mathsf{NL}\subseteq\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$
by Theorem 5.5. ∎

$\mathrm{I}$$\mathrm{I_{0}}$$\mathrm{I_{1}}$$\mathrm{I_{2}}$$\mathrm{N_{2}}$$\mathrm{N}$$\mathrm{V}$$\mathrm{V_{0}}$$\mathrm{V_{1}}$$\mathrm{V_{2}}$$\mathrm{L}$$\mathrm{L_{0}}$$\mathrm{L_{1}}$$\mathrm{L_{2}}$$\mathrm{L_{3}}$$\mathrm{E}$$\mathrm{E_{0}}$$\mathrm{E_{1}}$$\mathrm{E_{2}}$$\mathrm{D_{2}}$$\mathrm{S_{0}}$$\mathrm{S_{00}}$$\mathrm{S_{01}}$$\mathrm{S_{02}}$$\mathrm{S_{1}}$$\mathrm{S_{10}}$$\mathrm{S_{11}}$$\mathrm{S_{12}}$$\mathrm{D_{1}}$$\mathrm{D}$$\mathrm{S^{3}_{0}}$$\mathrm{S^{3}_{00}}$$\mathrm{S^{3}_{01}}$$\mathrm{S^{3}_{02}}$$\mathrm{S^{3}_{1}}$$\mathrm{S^{3}_{10}}$$\mathrm{S^{3}_{11}}$$\mathrm{S^{3}_{12}}$$\mathrm{S^{2}_{0}}$$\mathrm{S^{2}_{00}}$$\mathrm{S^{2}_{01}}$$\mathrm{S^{2}_{02}}$$\mathrm{S^{2}_{1}}$$\mathrm{S^{2}_{10}}$$\mathrm{S^{2}_{11}}$$\mathrm{S^{2}_{12}}$$\mathrm{M}$$\mathrm{M_{0}}$$\mathrm{M_{1}}$$\mathrm{M_{2}}$$\mathrm{BF}$$\mathrm{R_{0}}$$\mathrm{R_{1}}$$\mathrm{R_{2}}$

Solvable in $\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]$.
---
Requires monotone circuits of size $2^{\Omega(n^{\varepsilon})}$.
Trivial (i.e., a constant function).

Figure 2: Illustration of Theorem 5.8. The vertices are colored with the
_monotone circuit size_ complexity of deciding CSPs whose set of polymorphisms
corresponds to the label of the vertex.

######  Remark 5.9.

We remark that the lifting theorem of [31] (which is an ingredient in the
proof of Theorem 3.1) is only used to prove that the monotone complexity of
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is exponential when
$\mathsf{Pol}(S)\subseteq\mathrm{L_{3}}$. If we only care to show a
superpolynomial separation, then it suffices to apply the superpolynomial
lower bound for CSPs with counting proved in [27, 13] using the approximation
method. Indeed, we give an explicit proof in Appendix A. The same holds for
the consequences of this theorem (see Theorem 5.19).

###### Dichotomy for formulas.

Define
$\mathsf{3\mbox{-}Horn\mbox{-}SAT}_{n}:\left\\{0,1\right\\}^{2n^{3}+n}\to\left\\{0,1\right\\}$
as
$\mathsf{3\mbox{-}Horn\mbox{-}SAT}_{n}=\mathsf{CSP}\text{-}\mathsf{SAT}_{{\mathcal{H}}^{3}}^{n}$,
where

${\mathcal{H}}^{3}=\left\\{(\neg x_{1}\lor\neg x_{2}\lor x_{3}),(\neg
x_{1}\lor\neg x_{2}\lor\neg x_{3}),(x)\right\\}.$

The following is proved in [60, 31].

######  Theorem 5.10 ([60, 31]).

There exists $\varepsilon>0$ such that
$\mathsf{3\mbox{-}Horn\mbox{-}SAT}\in\mathsf{m}\mathsf{SIZE}[\mathsf{poly}]\setminus\mathsf{m}\mathsf{DEPTH}[o(n^{\varepsilon})]$.

###### Proof sketch.

Since $\mathrm{E_{2}}\subseteq\mathsf{Pol}({\mathcal{H}}^{3})$ (see, e.g.,
[23, Lemma 4.8]), the upper bound follows from Theorem 5.5. The lower bound
follows from a lifting theorem of [60, 31]. They show that the monotone
circuit-depth of $\mathsf{3\mbox{-}Horn\mbox{-}SAT}$ is at least the depth of
the smallest Resolution-tree refuting a so-called _pebbling formula_. Since
this formula requires Resolution-trees of depth $n^{\varepsilon}$, the lower
bound follows. ∎

Analogously to the previous section, we show that
$\mathsf{3\mbox{-}Horn\mbox{-}SAT}$ reduces to
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ whenever $\mathsf{Pol}(S)$ is small
enough, in a precise sense stated below. We then deduce the dichotomy for
formulas with a similar argument.

######  Lemma 5.11.

Let $S$ be a finite set of relations. If
$\mathsf{Pol}(S)\subseteq\mathrm{E_{2}}$ or
$\mathsf{Pol}(S)\subseteq\mathrm{V_{2}}$, then
$\mathsf{3\mbox{-}Horn\mbox{-}SAT}\leq^{\mathsf{m}\mathsf{NL}}_{m}\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$.

###### Proof.

We first consider the case $\mathsf{Pol}(S)\subseteq\mathrm{E_{2}}$. Note that
$\mathrm{E_{2}}\subseteq\mathsf{Pol}(\mathsf{3\mbox{-}Horn\mbox{-}SAT})$ (see,
e.g., [23, Lemma 4.8]). Therefore, from Lemma 5.4 we deduce that
$\mathsf{3\mbox{-}Horn\mbox{-}SAT}$ admits a reduction to
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ in $\mathsf{m}\mathsf{NL}$.

Now let
$\mathsf{3\mbox{-}AntiHorn\mbox{-}SAT}=\mathsf{CSP}\text{-}\mathsf{SAT}_{{\mathcal{A}}^{3}}$,
where ${\mathcal{A}}^{3}=\left\\{(x_{1}\lor x_{2}\lor\neg x_{3}),(x_{1}\lor
x_{2}\lor x_{3}),(\neg x)\right\\}$. Observe that a
${\mathcal{H}}^{3}$-formula $\varphi$ is satisfiable if and only if the
${\mathcal{A}}^{3}$-formula $\varphi(\neg x_{1},\dots,\neg x_{n})$ is
satisfiable. Therefore, we have
$\mathsf{3\mbox{-}Horn\mbox{-}SAT}\leq^{\mathsf{mProj}}_{m}\mathsf{3\mbox{-}AntiHorn\mbox{-}SAT}$.
Observing that $\mathrm{V_{2}}\subseteq\mathsf{Pol}({\mathcal{A}}^{3})$
(again, see e.g. [23, Lemma 4.8]), the result now follows from Lemma 5.4 and
the previous paragraph. ∎

######  Theorem 5.12 (Dichotomy for monotone formulas).

Let $S$ be a finite set of relations. If
$\mathsf{Pol}(S)\subseteq\mathrm{L_{3}}$, or
$\mathsf{Pol}(S)\subseteq\mathrm{V_{2}}$, or
$\mathsf{Pol}(S)\subseteq\mathrm{E_{2}}$, then there is a constant
$\varepsilon>0$ such that
$\mathsf{mDEPTH}({\mathsf{CSP}\text{-}\mathsf{SAT}_{S}})={\Omega(n^{\varepsilon})}$.
Otherwise, we have
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\in\mathsf{m}\mathsf{NL}\subseteq\mathsf{m}\mathsf{NC}^{2}\subseteq\mathsf{m}\mathsf{DEPTH}[\log^{2}n]$.

###### Proof.

We will first prove the lower bound. If
$\mathsf{Pol}(S)\subseteq\mathrm{L_{3}}$, the lower bound follows from Theorem
5.8. If $\mathsf{Pol}(S)\subseteq\mathrm{V_{2}}$ or
$\mathsf{Pol}(S)\subseteq\mathrm{E_{2}}$, the lower bound follows from
Theorems 5.10 and 5.11.

By inspecting Post’s lattice (Remark 5.1), we see that the remaning cases are:

  1. 1.

$\mathrm{I_{0}}\subseteq\mathsf{Pol}(S)$ or
$\mathrm{I_{1}}\subseteq\mathsf{Pol}(S)$. In both cases, any $\mathsf{CNF}(S)$
is trivially satisfiable.

  2. 2.

$\mathrm{S_{00}}\subseteq\mathsf{Pol}(S)$, or
$\mathrm{S_{10}}\subseteq\mathsf{Pol}(S)$, or
$\mathrm{D_{2}}\subseteq\mathsf{Pol}(S)$. In all of those three cases, we have
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\in\mathsf{m}\mathsf{NL}$ by Theorem 5.5.
∎

$\mathrm{I}$$\mathrm{I_{0}}$$\mathrm{I_{1}}$$\mathrm{I_{2}}$$\mathrm{N_{2}}$$\mathrm{N}$$\mathrm{V}$$\mathrm{V_{0}}$$\mathrm{V_{1}}$$\mathrm{V_{2}}$$\mathrm{L}$$\mathrm{L_{0}}$$\mathrm{L_{1}}$$\mathrm{L_{2}}$$\mathrm{L_{3}}$$\mathrm{E}$$\mathrm{E_{0}}$$\mathrm{E_{1}}$$\mathrm{E_{2}}$$\mathrm{D_{2}}$$\mathrm{S_{0}}$$\mathrm{S_{00}}$$\mathrm{S_{01}}$$\mathrm{S_{02}}$$\mathrm{S_{1}}$$\mathrm{S_{10}}$$\mathrm{S_{11}}$$\mathrm{S_{12}}$$\mathrm{D_{1}}$$\mathrm{D}$$\mathrm{S^{3}_{0}}$$\mathrm{S^{3}_{00}}$$\mathrm{S^{3}_{01}}$$\mathrm{S^{3}_{02}}$$\mathrm{S^{3}_{1}}$$\mathrm{S^{3}_{10}}$$\mathrm{S^{3}_{11}}$$\mathrm{S^{3}_{12}}$$\mathrm{S^{2}_{0}}$$\mathrm{S^{2}_{00}}$$\mathrm{S^{2}_{01}}$$\mathrm{S^{2}_{02}}$$\mathrm{S^{2}_{1}}$$\mathrm{S^{2}_{10}}$$\mathrm{S^{2}_{11}}$$\mathrm{S^{2}_{12}}$$\mathrm{M}$$\mathrm{M_{0}}$$\mathrm{M_{1}}$$\mathrm{M_{2}}$$\mathrm{BF}$$\mathrm{R_{0}}$$\mathrm{R_{1}}$$\mathrm{R_{2}}$

Solvable in
$\mathsf{m}\mathsf{NL}\subseteq\mathsf{m}\mathsf{DEPTH}[O(\log^{2}n)]$.
---
Requires monotone depth ${\Omega(n^{\varepsilon})}$.
Trivial (i.e., a constant function).

Figure 3: Illustration of Theorem 5.12. The vertices are colored with the
_monotone circuit depth_ complexity of deciding CSPs whose set of
polymorphisms corresponds to the label of the vertex.

###  5.4 Some auxiliary results

In this section, we prove auxiliary results needed in the proof of a more
general form of Theorem 1.4. In particular, we will prove that all
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ which are in $\mathsf{AC}^{0}$ are also
contained in $\mathsf{mAC}^{0}\subseteq\mathsf{m}\mathsf{NC}^{1}$. Moreover,
we show that, if
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\notin\mathsf{m}\mathsf{NC}^{1}$, then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is $\mathsf{L}$-hard under
$\leq^{\mathsf{AC}^{0}}_{m}\\!$ reductions.

We first observe that, when $\mathsf{COQ}(S_{1})\subseteq\mathsf{COQ}(S_{2})$,
there exists an efficient low-depth reduction from
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S_{1}}$ to
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S_{2}}$. This reduction, which will be
useful in this section, is more refined than the one given by Lemma 5.4. A
proof of the non-monotone version of this statement is found in [10,
Proposition 2.3], and we give a monotone version of this proof in Section B.2.

######  Lemma 5.13 ([10, Proposition 2.3]).

If $\mathsf{COQ}(S_{1})\subseteq\mathsf{COQ}(S_{2})$, then there exists a
constant $C\in{\mathbb{N}}$ such that
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S_{1}}^{n}\leq^{\mathsf{mOR}}_{m}\mathsf{CSP}\text{-}\mathsf{SAT}_{S_{2}}^{Cn}$.

###### Proof.

We defer the proof to Section B.2. ∎

We now recall some lemmas from [2], and prove a few consequences from them. We
say that a set $S$ of relations _can express equality_ if
$\left\\{=\right\\}\subseteq\mathsf{COQ}(S)$.

######  Lemma 5.14 ([2]).

Let $S$ be a finite set of relations. Suppose
$\mathrm{S_{02}}\subseteq\mathsf{Pol}(S)$
($\mathrm{S_{12}}\subseteq\mathsf{Pol}(S)$, resp.) and that $S$ cannot express
equality. Then there exists $k\geq 2$ such that
$S\subseteq\mathsf{COQ}(\left\\{\mathsf{OR}^{k},x,\neg x\right\\})$
($S\subseteq\mathsf{COQ}(\left\\{\mathsf{NAND}^{k},x,\neg x\right\\})$,
resp.).

###### Proof.

Follows from the proof of Lemma 3.8 of [2]. ∎

######  Lemma 5.15.

Let $S$ be a finite set of relations such that
$\mathsf{Pol}(S)\subseteq\mathrm{R_{2}}$. If
$\mathrm{S_{02}}\subseteq\mathsf{Pol}(S)$ or
$\mathrm{S_{12}}\subseteq\mathsf{Pol}(S)$, and $S$ cannot express equality,
then $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\in\mathsf{mAC}^{0}_{3}$.

###### Proof.

We write the proof in the case $\mathrm{S_{02}}\subseteq\mathsf{Pol}(S)$. The
other case is analogous.

From Lemmas 5.13 and 5.14 and Items (iv) and (v) of Lemma 5.3, we get that
there is a monotone OR-reduction from $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$
to $\mathsf{CSP}\text{-}\mathsf{SAT}_{\left\\{\mathsf{OR}^{k},x,\neg
x\right\\}}$ for some $k$. However, an $\left\\{\mathsf{OR}^{k},x,\neg
x\right\\}$-formula is unsatisfiable iff there exists a literal and its
negation as a constraint in the formula, or if there exists a disjunction in
the formula such that every one of its literals appears negatively as a
constraint. This condition can be easily checked by a polynomial-size monotone
DNF. Composing the monotone DNF with the monotone OR-reduction, we obtain a
depth-3 $\mathsf{AC}^{0}$ circuit computing
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$. ∎

######  Lemma 5.16 ([2, Lemma 3.8]).

Let $S$ be a finite set of relations such that
$\mathsf{Pol}(S)\subseteq\mathrm{R_{2}}$. If
$\mathrm{S_{02}}\subseteq\mathsf{Pol}(S)$ or
$\mathrm{S_{12}}\subseteq\mathsf{Pol}(S)$, and $S$ can express equality, then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is $\mathsf{L}$-hard under
$\leq^{\mathsf{AC}^{0}}_{m}\\!$ reductions.

######  Lemma 5.17.

Let $S$ be a finite set of relations. If
$\mathrm{S_{02}}\not\subseteq\mathsf{Pol}(S)$ and
$\mathrm{S_{12}}\not\subseteq\mathsf{Pol}(S)$, then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is $\mathsf{L}$-hard or trivial.

###### Proof.

This follows by inspecting Post’s lattice (Figure 1) and the classification
theorem (Theorem 5.6). ∎

We may now prove the main result of this subsection.

######  Theorem 5.18.

We have $\mathsf{CSP}\cap\mathsf{AC}^{0}\subseteq\mathsf{mAC}^{0}_{3}$.
Moreover, if $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\notin\mathsf{mAC}^{0}_{3}$,
then $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is $\mathsf{L}$-hard under
$\leq^{\mathsf{AC}^{0}}_{m}\\!$ reductions.

###### Proof.

Let $S$ be a finite set of relations. If
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\not\in\mathsf{mAC}^{0}_{3}$, then, by
Lemma 5.15, at least one of the following cases hold:

  1. 1.

$\mathrm{S_{02}}\subseteq\mathsf{Pol}(S)\subseteq\mathrm{R_{2}}$ or
$\mathrm{S_{12}}\subseteq\mathsf{Pol}(S)\subseteq\mathrm{R_{2}}$, and $S$ can
express the equality relation;

  2. 2.

$\mathrm{S_{02}}\not\subseteq\mathsf{Pol}(S)\subseteq\mathrm{R_{2}}$ and
$\mathrm{S_{12}}\not\subseteq\mathsf{Pol}(S)\subseteq\mathrm{R_{2}}$.

  3. 3.

$\mathsf{Pol}(S)\not\subseteq\mathrm{R_{2}}$.

Since $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is not trivial, we obtain that
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is $\mathsf{L}$-hard in the first two
cases by Lemmas 5.16 and 5.17, and it’s easy to check that
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is also $\mathsf{L}$-hard in the third
case by inspecting Post’s lattice (Figure 1) and the classification theorem
(Theorem 5.6). Since $\mathsf{L}\not\subseteq\mathsf{AC}^{0}$, this also
implies that, if $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\in\mathsf{AC}^{0}$,
then $\mathrm{S_{02}}\subseteq\mathsf{Pol}(S)\subseteq\mathrm{R_{2}}$ or
$\mathrm{S_{12}}\subseteq\mathsf{Pol}(S)\subseteq\mathrm{R_{2}}$, and $S$
cannot express the equality relation. Lemma 5.15 again gives
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\in\mathsf{mAC}^{0}_{3}$. ∎

###  5.5 Consequences for monotone circuit lower bounds via lifting

We now prove a stronger form of Theorem 1.4. In the previous section, we
showed that $\mathsf{CSP}\cap\mathsf{AC}^{0}\subseteq\mathsf{mAC}^{0}$. In
particular, this means that there does not exist a finite set of relations $S$
such that $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ separates $\mathsf{AC}^{0}$
and $\mathsf{m}\mathsf{NC}^{1}$, a separation which we proved in Theorem 1.1.
We will also observe that, if
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\notin\mathsf{m}\mathsf{NC}^{2}$, then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is $\oplus\mathsf{L}$-hard.

######  Theorem 5.19.

Let $S$ be a finite set of Boolean relations.

  1. 1.

If $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\notin\mathsf{mAC}^{0}_{3}$ then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is $\mathsf{L}$-hard under
$\leq^{\mathsf{AC}^{0}}_{m}\\!$ reductions.

  2. 2.

If $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\notin\mathsf{m}\mathsf{NC}^{2}$, then
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is $\oplus\mathsf{L}$-hard under
$\leq^{\mathsf{AC}^{0}}_{m}\\!$ reductions.

###### Proof.

Item (1) follows from Theorem 5.18. To prove item (2), suppose that
$\mathsf{mDEPTH}({\mathsf{CSP}\text{-}\mathsf{SAT}_{S}})={\omega(\log^{2}n)}$.
Then, by Theorem 5.12, we conclude that
$\mathsf{Pol}(S)\subseteq\mathrm{L_{3}}$, or
$\mathsf{Pol}(S)\subseteq\mathrm{V_{2}}$, or
$\mathsf{Pol}(S)\subseteq\mathrm{E_{2}}$. Theorem 5.6 implies that
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is $\oplus\mathsf{L}$-hard. ∎

Further Discussion. We recall the discussion of Section 1.1.3. We introduced
and defined the functions $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ in that
section, as a way to capture monotone circuit lower bounds proved via lifting.
This in particular captures the monotone function
$\mathsf{3\mbox{-}XOR\mbox{-}SAT}$, which was proved in [31] to require
monotone circuit lower bounds of size $2^{n^{\Omega(1)}}$ to compute, even
though $\oplus\mathsf{L}$-machines running in polynomial-time can compute it.
Theorem 5.19 proves that this separation between monotone and non-monotone
circuit lower bounds cannot be improved by varying the set of relations $S$,
as we argue below.

There are two ways one could try to find a function in $\mathsf{AC}^{0}$ with
large monotone complexity using a $\mathsf{CSP}\text{-}\mathsf{SAT}$ function.
First, one could try to define a set of relations $S$ such that
$\mathsf{CSP}\text{-}\mathsf{SAT}_{S}\in\mathsf{AC}^{0}$, but the monotone
complexity of $\mathsf{CSP}\text{-}\mathsf{SAT}_{S}$ is large. However, Item
(1) of Theorem 5.19 proves that this is impossible, as any
$\mathsf{CSP}\text{-}\mathsf{SAT}$ function outside of $\mathsf{mAC}^{0}$ is
$\mathsf{L}$-hard under simple reductions and, therefore, cannot be computed
in $\mathsf{AC}^{0}$.

Secondly, one could try to be apply the arguments of Section 3, consisting of
a padding trick and a simulation theorem. When $S$ is the set of 3XOR
relations, then indeed we obtain a function in $\mathsf{AC}^{0}[\oplus]$ with
superpolynomial monotone circuit complexity, as proved in Theorem 3.1.
However, Item (2) of Theorem 5.19 proves that this is best possible, as any
$\mathsf{CSP}\text{-}\mathsf{SAT}$ function which admits a superpolynomial
monotone circuit lower bound must be $\oplus\mathsf{L}$-hard and, therefore,
at least as hard as $\mathsf{3\mbox{-}XOR\mbox{-}SAT}$ for non-monotone
circuits. Item (2) also shows that even $\mathsf{CSP}\text{-}\mathsf{SAT}$
functions with a $\omega(\log^{2}n)$ monotone depth lower bound must be
$\oplus\mathsf{L}$-hard, which suggests that the arguments of Section 3
applied to a $\mathsf{CSP}\text{-}\mathsf{SAT}$ function are not able to prove
the separation of Theorem 3.3.

A caveat to these impossibility results is in order. First, we only study
Boolean-valued CSPs here, though the framework of lifting can also be applied
in the context of non-Boolean CSPs. It’s not clear if non-Boolean CSPs exhibit
the same dichotomies for monotone computation we proved in this section. We
remark that Schaefer’s dichotomy for Boolean-valued CSPs [67] has been
extended to non-Boolean CSPs [72, 18].

Secondly, the instances of $\mathsf{CSP}\text{-}\mathsf{SAT}$ generated by
lifting do not cover the entirety of the minterms and maxterms of
$\mathsf{CSP}\text{-}\mathsf{SAT}$. In particular, our results do not rule out
the possibility that a clever interpolation of the instances generated by
lifting may give rise to a function that is easier to compute by non-monotone
circuits, and therefore bypasses the hardness results of Theorem 5.19. One
example is the Tardós function [69]. A lifting theorem applied to a Pigeonhole
Principle formula can be used to prove a lower bound on the size of monotone
circuits that accept cliques of size $k$ and reject graphs that are
$(k-1)$-colorable, for some $k=n^{\varepsilon}$ [60, 59]. A natural
interpolation for these instances would be the $k\mbox{-}\\!\mathsf{Clique}$
function, which, being $\mathsf{NP}$-complete, would be related to an
$\mathsf{NP}$-complete $\mathsf{CSP}\text{-}\mathsf{SAT}$. However, as proved
by [69], there is a monotone function in $\mathsf{P}$ which has the same
output behaviour over these instances.

## References

  * AB [87] Noga Alon and Ravi B. Boppana.  The monotone circuit complexity of boolean functions.  Combinatorica, 7(1):1–22, 1987.
  * ABI+ [09] Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, and Heribert Vollmer.  The complexity of satisfiability problems: Refining Schaefer’s theorem.  J. Comput. Syst. Sci., 75(4):245–254, 2009.
  * AG [87] Miklós Ajtai and Yuri Gurevich.  Monotone versus positive.  J. Assoc. Comput. Mach., 34(4):1004–1015, 1987.
  * AHM+ [08] Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, and Michael E. Saks.  Minimizing disjunctive normal form formulas and AC0 circuits given a truth table.  SIAM J. Comput., 38(1):63–84, 2008.
  * AK [11] Jin Akiyama and Mikio Kano.  Factors and Factorizations of Graphs, volume 2031 of Lecture Notes in Mathematics.  Springer Berlin Heidelberg, Berlin, Heidelberg, 2011.
  * AKR+ [01] Eric Allender, Michal Koucký, Detlef Ronneburger, Sambuddha Roy, and V. Vinay.  Time-space tradeoffs in the counting hierarchy.  In Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, Illinois, USA, June 18-21, 2001, pages 295–302. IEEE Computer Society, 2001.
  * AKS [83] Miklós Ajtai, János Komlós, and Endre Szemerédi.  An $O(n\log n)$ sorting network.  In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 1–9. ACM, 1983.
  * And [85] Alexander E Andreev.  On a method for obtaining lower bounds for the complexity of individual monotone functions.  Doklady Akademii Nauk SSSR, 282:1033–1037, 1985.
  * BCRV [03] Elmar Böhler, Nadia Creignou, Steffen Reith, and Heribert Vollmer.  Playing with boolean blocks, part i: Post’s lattice with applications to complexity theory.  SIGACT News, 2003.
  * BCRV [04] Elmar Böhler, Nadia Creignou, Steffen Reith, and Heribert Vollmer.  Playing with boolean blocks, part ii: Constraint satisfaction problems.  ACM SIGACT-Newsletter, 35, 2004.
  * BDHM [92] Gerhard Buntrock, Carsten Damm, Ulrich Hertrampf, and Christoph Meinel.  Structure and importance of logspace-mod class.  Math. Syst. Theory, 25(3):223–237, 1992.
  * Ber [82] S. J. Berkowitz.  On some relationships between monotone and non-monotone circuit complexity.  Technical Report. University of Toronto, 1982.
  * BGW [99] László Babai, Anna Gál, and Avi Wigderson.  Superpolynomial lower bounds for monotone span programs.  Combinatorica, 19(3):301–319, 1999.
  * BHST [14] Eric Blais, Johan Håstad, Rocco A. Servedio, and Li-Yang Tan.  On DNF approximators for monotone boolean functions.  In International Colloquium on Automata, Languages, and Programming _(ICALP)_ , pages 235–246, 2014.
  * BL [88] Josh Cohen Benaloh and Jerry Leichter.  Generalized secret sharing and monotone functions.  In Advances in Cryptology _(CRYPTO)_ , pages 27–35, 1988.
  * BST [13] Eric Blais, Dominik Scheder, and Li-Yang Tan.  Ajtai-gurevich redux. Manuscript.  2013\.
  * BT [96] Nader H. Bshouty and Christino Tamon.  On the Fourier spectrum of monotone functions.  J. ACM, 43(4):747–770, 1996.
  * Bul [17] Andrei A. Bulatov.  A dichotomy theorem for nonuniform csps.  In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 319–330. IEEE Computer Society, 2017.
  * Bul [18] Andrei A. Bulatov.  Constraint satisfaction problems: complexity and algorithms.  ACM SIGLOG News, 5(4):4–24, 2018.
  * CDM [21] Arkadev Chattopadhyay, Rajit Datta, and Partha Mukhopadhyay.  Lower bounds for monotone arithmetic circuits via communication complexity.  In STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 786–799. ACM, 2021\.
  * CHO+ [20] Lijie Chen, Shuichi Hirahara, Igor C. Oliveira, Ján Pich, Ninad Rajgopal, and Rahul Santhanam.  Beyond Natural Proofs: Hardness Magnification and Locality.  In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 151, pages 70:1–70:48, 2020.
  * CKR [20] Bruno Pasqualotto Cavalar, Mrinal Kumar, and Benjamin Rossman.  Monotone circuit lower bounds from robust sunflowers.  In LATIN 2020: Theoretical Informatics - 14th Latin American Symposium, São Paulo, Brazil, January 5-8, 2021, Proceedings, volume 12118 of Lecture Notes in Computer Science, pages 311–322. Springer, 2020\.
  * CKS [01] Nadia Creignou, Sanjeev Khanna, and Madhu Sudan.  Complexity classifications of Boolean constraint satisfaction problems, volume 7 of SIAM monographs on discrete mathematics and applications.  SIAM, 2001.
  * COS [17] Xi Chen, Igor C. Oliveira, and Rocco A. Servedio.  Addition is exponentially harder than counting for shallow monotone circuits.  In STOC’17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1232–1245. ACM, New York, 2017\.
  * CZ [16] Eshan Chattopadhyay and David Zuckerman.  Explicit two-source extractors and resilient functions.  In Symposium on Theory of Computing _(STOC)_ , pages 670–683, 2016.
  * dRGR [22] Susanna F. de Rezende, Mika Göös, and Robert Robere.  Guest column: Proofs, circuits, and communication.  SIGACT News, 53(1):59–82, 2022.
  * FV [98] Tomás Feder and Moshe Y. Vardi.  The computational structure of monotone monadic SNP and constraint satisfaction: A study through datalog and group theory.  SIAM J. Comput., 28(1):57–104, 1998.
  * GGLR [98] Oded Goldreich, Shafi Goldwasser, Eric Lehman, and Dana Ron.  Testing monotonicity.  In Symposium on Foundations of Computer Science, _(FOCS)_ , pages 426–435, 1998.
  * GI [12] Oded Goldreich and Rani Izsak.  Monotone circuits: One-way functions versus pseudorandom generators.  Theory Comput., 8(1):231–238, 2012.
  * GJW [18] Mika Göös, Rahul Jain, and Thomas Watson.  Extension complexity of independent set polytopes.  SIAM J. Comput., 47(1):241–269, 2018.
  * GKRS [19] Mika Göös, Pritish Kamath, Robert Robere, and Dmitry Sokolov.  Adventures in monotone complexity and TFNP.  In 10th Innovations in Theoretical Computer Science, volume 124 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 38, 19\. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019.
  * GMOR [15] Siyao Guo, Tal Malkin, Igor C. Oliveira, and Alon Rosen.  The power of negations in cryptography.  In Theory of Cryptography Conference _(TCC)_ , pages 36–65, 2015.
  * GS [92] Michelangelo Grigni and Michael Sipser.  Monotone complexity.  In Proceedings of the London Mathematical Society Symposium on Boolean Function Complexity, page 57–75, USA, 1992. Cambridge University Press.
  * Hås [86] Johan Håstad.  Almost optimal lower bounds for small depth circuits.  In Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA, pages 6–20, 1986.
  * Hir [22] Shuichi Hirahara.  NP-hardness of learning programs and partial MCSP.  In Symposium on Foundations of Computer Science _(FOCS)_ , 2022\.
  * HWWY [94] Johan Håstad, Ingo Wegener, Norbert Wurm, and Sang-Zin Yi.  Optimal depth, very small size circuits for symmetric functions in AC0.  Inf. Comput., 108(2):200–211, 1994.
  * IKL+ [19] Christian Ikenmeyer, Balagopal Komarath, Christoph Lenzen, Vladimir Lysikov, Andrey Mokhov, and Karteek Sreenivasaiah.  On the complexity of hazard-free circuits.  J. ACM, 66(4):25:1–25:20, 2019.
  * JCG [97] Peter Jeavons, David Cohen, and Marc Gyssens.  Closure properties of constraints.  J. ACM, 44(4):527–548, jul 1997.
  * Jea [98] Peter Jeavons.  On the algebraic structure of combinatorial problems.  Theor. Comput. Sci., 200(1-2):185–204, 1998.
  * JLL [76] Neil D. Jones, Y. Edmund Lien, and William T. Laaser.  New problems complete for nondeterministic log space.  Math. Syst. Theory, 10:1–17, 1976.
  * Joh [03] Jan Johannsen.  The complexity of satisfiability problems with two occurrences.  Unpublished Manuscript, 2003.
  * Juk [12] Stasys Jukna.  Boolean Function Complexity - Advances and Frontiers.  Springer, 2012.
  * Kra [97] Jan Krajíček.  Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic.  J. Symbolic Logic, 62(2):457–486, 1997.
  * KS [92] Bala Kalyanasundaram and Georg Schnitger.  The probabilistic communication complexity of set intersection.  SIAM J. Discret. Math., 5(4):545–557, 1992.
  * Kup [21] Denis Kuperberg.  Positive first-order logic on words.  In Symposium on Logic in Computer Science _(LICS)_ , pages 1–13, 2021.
  * Kup [22] Denis Kuperberg.  Positive first-order logic on words and graphs.  CoRR, abs/2201.11619, 2022.
  * KW [93] Mauricio Karchmer and Avi Wigderson.  On span programs.  In Structure in Complexity Theory Conference _(CCC)_ , pages 102–111, 1993.
  * LT [09] Benoît Larose and Pascal Tesson.  Universal algebra and hardness results for constraint satisfaction problems.  Theor. Comput. Sci., 410(18):1629–1647, 2009.
  * Oko [82] E. A. Okol’nishnikova.  The effect of negations on the complexity of realization of monotone Boolean functions by formulas of bounded depth.  Metody Diskret. Analiz., (38):74–80, 1982.
  * Oli [15] Igor C. Oliveira.  Unconditional lower bounds in complexity theory, 2015.  (PhD Thesis, Columbia University).
  * OSS [19] Igor C. Oliveira, Rahul Santhanam, and Srikanth Srinivasan.  Parity helps to compute majority.  In 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA, pages 23:1–23:17, 2019.
  * Pos [41] Emil L. Post.  The Two-Valued Iterative Systems of Mathematical Logic. (AM-5).  Princeton University Press, 1941.
  * PR [17] Toniann Pitassi and Robert Robere.  Strongly exponential lower bounds for monotone computation.  In Symposium on Theory of Computing _(STOC)_ , pages 1246–1255, 2017.
  * Pud [97] Pavel Pudlák.  Lower bounds for resolution and cutting plane proofs and monotone computations.  J. Symb. Log., 62(3):981–998, 1997.
  * Qui [53] W. V. Quine.  Two theorems about truth functions.  Bol. Soc. Mat. Mexicana, 10:64–70, 1953.
  * [56] A. A. Razborov.  Lower bounds on the monotone complexity of some Boolean functions.  Dokl. Akad. Nauk SSSR, 281(4):798–801, 1985.
  * [57] Alexander A Razborov.  Lower bounds on monotone complexity of the logical permanent.  Mathematical Notes of the Academy of Sciences of the USSR, 37(6):485–493, 1985.
  * Rei [05] Omer Reingold.  Undirected st-connectivity in log-space.  In Harold N. Gabow and Ronald Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 376–385. ACM, 2005.
  * Rez [23] Susanna Rezende.  Personal communication, 2023.
  * RM [99] Ran Raz and Pierre McKenzie.  Separation of the monotone NC hierarchy.  Combinatorica, 19(3):403–435, 1999.
  * [61] Benjamin Rossman.  Homomorphism preservation theorems.  J. ACM, 55(3):Art. 15, 53, 2008.
  * [62] Benjamin Rossman.  On the constant-depth complexity of $k$-clique.  In Symposium on Theory of Computing _(STOC)_ , pages 721–730, 2008.
  * [63] Benjamin Rossman.  An entropy proof of the switching lemma and tight bounds on the decision-tree size of AC0.  2017\.
  * [64] Benjamin Rossman.  An improved homomorphism preservation theorem from lower bounds in circuit complexity.  In Innovations in Theoretical Computer Science Conference _(ITCS)_ , pages 27:1–27:17, 2017.
  * RPRC [16] Robert Robere, Toniann Pitassi, Benjamin Rossman, and Stephen A. Cook.  Exponential lower bounds for monotone span programs.  In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 406–415. IEEE Computer Society, 2016.
  * RW [92] Ran Raz and Avi Wigderson.  Monotone circuits for matching require linear depth.  J. ACM, 39(3):736–744, 1992.
  * Sch [78] Thomas J. Schaefer.  The complexity of satisfiability problems.  In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 216–226. ACM, 1978.
  * Sto [95] Alexei P. Stolboushkin.  Finitely monotone properties.  In Symposium on Logic in Computer Science _(LICS)_ , pages 324–330, 1995.
  * Tar [88] É. Tardos.  The gap between monotone and nonmonotone circuit complexity is exponential.  Combinatorica, 8(1):141–142, 1988.
  * Urq [87] Alasdair Urquhart.  Hard examples for resolution.  J. ACM, 34(1):209–219, 1987.
  * Val [80] Leslie G. Valiant.  Negation can be exponentially powerful.  Theor. Comput. Sci., 12:303–314, 1980.
  * Zhu [17] Dmitriy Zhuk.  A proof of CSP dichotomy conjecture.  In Chris Umans, editor, 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 331–342. IEEE Computer Society, 2017.

##  Appendix A A Lower Bound for $\mathsf{3\mbox{-}XOR\mbox{-}SAT}$ Using the
Approximation Method

As discussed in Section 1.1.3, [31] obtained an exponential lower bound on the
monotone circuit size of the function $\mathsf{3\mbox{-}XOR\mbox{-}SAT}$ using
techniques from communication complexity and lifting. Here we observe that a
weaker but still super-polynomial lower bound can be proved using the
approximation method.

First, we recall the function
$\mathsf{OddFactor}_{n}:\left\\{0,1\right\\}^{\binom{n}{2}}\to\left\\{0,1\right\\}$
of Section 3.2, which accepts a given graph if the graph contains an _odd
factor_ , which is a spanning subgraph in which the degree of every vertex is
odd. For convenience, in this section we consider a weaker version of