# Lower bounds on monotone space complexity

The monotone space complexity of a language $L \subseteq \Sigma^*$ can be defined in terms of monotone switching networks (see e.g. "Average Case Lower Bounds for Monotone Switching Networks" by Filmus et al.). This notion is linked to the monotone $NC$ hierarchy and may have applications to the non-monotone setting for which most questions are open.

Here is an equivalent definition in term of circuits. Let $K$ be a circuit (or dag) whose arcs are labelled by elements of $[n] \times \Sigma$, and which has a single root node $r$. We say that $K$ accepts a word $w \in \Sigma^n$ iff there is a root-leaf path $P$ in $K$ whose sequence of labels matches $w$, i.e. for each label $(i,a)$ in $P$ we have $w[i] = a$. Now, given a language $L$, for each integer $n$ we define its $n$-slice complexity $C_L(n)$ as the minimum size of a circuit accepting exactly the words in $L \cap \Sigma^n$. We can put some restrictions on this notion, for instance by requiring that the circuits are read-once, meaning that each accepting path makes a single access to a given position. This leads to a second complexity measure $C'_L(n)$ which seems easier to analyze, as illustrated below.

An example is the Perfect Matching problem ($PM$), which can be shown to have monotone complexity $C'_{PM}(n) = 2^{\Omega(n)}$ as follows. Let $PM_n$ denote the slice of the language corresponding to bipartite graphs $G$ with $n$ vertices on each side of the bipartition (denoted by $A,B$). Consider a circuit $K$ accepting it. Given an integer $k$, let $\mathcal{P}_k$ denote the set of paths of length $k$ in $K$ starting from the root, and let $\mathcal{T}_k$ denote the pair of sets $(S,T)$ with $S \subseteq A, T \subseteq B$ and $|S| = |T| = k$. By monotonicity, we can make the following assumption:

(*) for each node $u$ of depth $k$, there is a tuple $t = (S,T) \in \mathcal{T}_k$ such that each path $P \in \mathcal{P}_k$ leading to $u$ is labeled by a permutation $\sigma_P : S \rightarrow T$.

Indeed, if there were two different paths leading to $u$ corresponding to different tuples, one of them could be extended to a function that is not a permutation (and thus would recognize an $n$-edges graph that is not a matching).

Now observe that we must have the following "coverage" property: for each permutation $\sigma : A \rightarrow B$, there should exist some path $P \in \mathcal{P}_k$ such that $\sigma$ extends $\sigma_P$. Observe that a given permutation $\sigma_P$ can be extended to at most $(n-k)!$ different permutations, and that a given tuple in $\mathcal{T}_k$ can induce at most $k!$ different permutations. This implies that the number of nodes at depth $k$ is at least $\frac{n!}{k! (n-k)!}$. In particular, the number of nodes at level $\frac{n}{2}$ is at least $\frac{n!}{(\frac{n}{2})!^2} = 2^{\Omega(n)}$.

There are two things I would like to understand: (i) why does this reasoning break down for read-many / nonmonotone space complexity, (ii) how does it relate to known lower bounds for the monotone space complexity of $PM$.

In the read-once case, even the Exact PM (accept a graph iff it is a perfect matching) requires exponential size (by the same argument as yours). But if we allow negations, then EPM can be computed by a circuit of size $O(n^3)$: check if every node in A has degree at least one, and if every node in B has degree at most one. The resulting switching network is "almost read-once": every consistent path is read -once. Search term "null-path" here for more information.
To question (ii): I haven't understood what "it" here refers to? But as far as I know, the $n^{\Omega(\log n)}$ lower bound of Razborov (for monotone circuit size of PM) remains the strongest one. Even though monotone switching networks constitute a special case of monotone circuits (where one input of each AND gate must be a variable), no stronger lower bounds for PM are known here.