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.

  • 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


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

  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.