0
$\begingroup$

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?

$\endgroup$
5
  • 1
    $\begingroup$ 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 $\endgroup$ Jun 9 at 8:29
  • $\begingroup$ I tried looking at the paper. I have no idea of what the upper bounds are. I am not seeking lower bounds. $\endgroup$
    – Mr.
    Jun 9 at 9:18
  • $\begingroup$ 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. $\endgroup$
    – Mr.
    Jun 9 at 9:28
  • $\begingroup$ All the information you need is in the paper. It might require some work extracting it. $\endgroup$ Jun 9 at 9:37
  • $\begingroup$ The section on $NL\subseteq CC$ on pp. $35$ is straightforward but I still do not really see depth to be $o(n)$. $\endgroup$
    – Mr.
    Jun 9 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.