5
$\begingroup$

Branching programs are usually used as a computation model for non-uniform logarithmic space $\mathsf{L}/\mathrm{poly}$. Is there a reference about Boolean circuits corresponding to $\mathsf{L}/\mathrm{poly}$?

Intuitively, bounded space Turing machines seem to correspond to bounded width Boolean circuits, but I can't find a reference. Is there a reason that branching programs are used for $\mathsf{L}/\mathrm{poly}$ and Boolean circuits are not used?

[Addition after Sam McGuire's answer (in comments)]

Actually, I'm most interested in Boolean circuits corresponding to $\mathsf{L}/\mathrm{quasipoly}$. I guess that it is quasipolynomial-size $O(\log n)$-width Boolean circuits.

I would like to know that, whether it is right or not, whether I should prove it myself or not, whether it is known and there's a reference or not.

$\endgroup$
3
  • 7
    $\begingroup$ Yes, it corresponds to log-width polynomial-size (non-uniform) circuits. The proof is pretty straightforward, which can be seen in On Simultaneous Resource Bounds by Nick Pippenger (I can't find a free .pdf version). $\endgroup$ Oct 4, 2018 at 16:44
  • 1
    $\begingroup$ @Sam McGuire: Thank you. It seems to be an answer. I'll read it. If there is another free reference, it's continually welcom. (Actually, I'm interested in something beyond L/poly. I'll add it to my question post.) $\endgroup$ Oct 4, 2018 at 17:35
  • $\begingroup$ Of course, non-free references are also welcome. $\endgroup$ Oct 5, 2018 at 3:48

1 Answer 1

7
$\begingroup$

$\mathsf{L}/\mathrm{poly}$ can be characterized by polynomial size skew circuits. A boolean circuit is called skew if every AND-gate has at most one child that is not an input gate. Skew circuits and branching programs can simulate each other with polynomial blow-up, so polynomial size skew circuits and branching programs compute the same class of functions, which is $\mathsf{L}/\mathrm{poly}$.

A proof of these simulations can e.g. be found in this paper by Balaji, Krebs and Limaye.

$\endgroup$
5
  • $\begingroup$ Thank you. While it seems to answer my question, I'm especially interested in the case of bounded width (not skew) circuits. In more details, I'm interested in L/quasipoly as I have written to the question post. I have thought that BPs can't treat L/quasipoly or it's difficult. Skew circuits are via BPs. I would like to know more direct connections of space and circuit width. $\endgroup$ Oct 5, 2018 at 9:50
  • $\begingroup$ "it's difficult" -> "it needs another task" $\endgroup$ Oct 5, 2018 at 10:00
  • 1
    $\begingroup$ @HirokiMorizumi There is this hierarchy of Steve's classes $\mathsf{SC}$, characterized by bounded width circuits (not skew), where $\mathsf{SC^i}$ corresponds to $\mathsf{TimeSpace}(\poly(n), O(\log^i{n})$. But if you want a characterization of L/poly, it is exactly equivalent to branching programs, which are exactly the same as skew circuits as Jan points out above. $\endgroup$
    – Nikhil
    Oct 5, 2018 at 11:15
  • $\begingroup$ Didn't see @Sam Mcguire's comment above, which gives a clearer picture. $\endgroup$
    – Nikhil
    Oct 5, 2018 at 11:17
  • $\begingroup$ @Nikhil: Do you know a reference? I also have partial knowledge. $\endgroup$ Oct 5, 2018 at 12:14

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .