# What is the depth of comparator circuit required in Gale Shapely and STCONN?

Stable matching problem and $$STCONN$$ can be solved using comparator circuits (refer https://arxiv.org/abs/1208.2721).

1. What is the depth of the $$CC$$ circuit necessary for stable matching? Is it in $$CC^1$$ or in other words $$O(\log (n))$$ depth comparator circuit?

2. What is the depth of the $$CC$$ circuit necessary for $$NL$$? Is it in $$CC^1$$ or in other words $$O(\log (n))$$ depth comparator circuit?

Notice $$STCONN$$ is complete for $$NL$$ and is in $$AC^1\subseteq NC^2$$ which perfect matching (not stable) is in $$NC^2$$ and is hard for $$NL$$.

If 1. and 2. and not in $$CC^1$$ then what is the minimum $$CC^i$$ upper bound?

• Have you tried looking at the proofs in the paper? They give some upper bounds. You shouldn't expect any lower bounds, since non-trivial lower bounds are difficult. State-of-the-art lower bounds can be found in Gál and Robere, Lower Bounds for (Non-monotone) Comparator Circuits – Yuval Filmus Jun 9 at 8:29
• I tried looking at the paper. I have no idea of what the upper bounds are. I am not seeking lower bounds. – Bread Winner Jun 9 at 9:18
• When I think of $NC$ I think of $NC^k$ at a particular $k$. The $NL$ reduction to $CC$ illustrated on pp. $35$ in arxiv.org/abs/1208.2721 for $n=5$ has at least $5$ layers and so depth for general $n$ is not appearing to be $polylogarithmic$. I similarly do not get insight for perfect matching. – Bread Winner Jun 9 at 9:28
• All the information you need is in the paper. It might require some work extracting it. – Yuval Filmus Jun 9 at 9:37
• The section on $NL\subseteq CC$ on pp. $35$ is straightforward but I still do not really see depth to be $o(n)$. – Bread Winner Jun 9 at 9:45