<p>This not quite an answer, but rather an "extended comment".</p>

<p>To question (i): property (*) holds because of read-once, not because of the monotonicity, and this is why the argument fails in the read-many (even monotone) case: then the combined paths need <em>not</em> be PMs, they can be <em>arbitrary</em> graphs <em>containing</em> a PM.  </p>

<p>In the read-once case, even the Exact PM (accept a graph iff it <em>is</em> 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" <a href="http://books.google.de/books?id=rHn7hXxyPAkC&amp;printsec=frontcover&amp;hl=de&amp;source=gbs_ge_summary_r&amp;cad=0#v=onepage&amp;q&amp;f=false">here</a> for more information.  </p>

<p>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. </p>

CC BY-SA 3.0
2014-03-21T11:45:16.737Z
2014-03-21T11:45:16.737Z
Stasys
<p>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.</p>

<p>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.</p>

<p>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:</p>

<p>(*) 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$.</p>

<p>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).</p>

<p>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)}$.</p>

<p>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$.</p>

<circuit-complexity>
Lower bounds on monotone space complexity
NisaiVloot
# Lower bounds on monotone space complexity

(Asked by: username_0 on 2014-03-20)

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$.

**Tags:** circuit-complexity

---

## 1 answers

### Answer by username_1 on 2014-03-21. Score: 6

This not quite an answer, but rather an "extended comment".

To question (i): property (\*) holds because of read-once, not because of the monotonicity, and this is why the argument fails in the read-many (even monotone) case: then the combined paths need *not* be PMs, they can be *arbitrary* graphs *containing* a 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](http://books.google.de/books?id=rHn7hXxyPAkC&printsec=frontcover&hl=de&source=gbs_ge_summary_r&cad=0#v=onepage&q&f=false) 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.


---

