# Boolean circuits which correspond to L/poly

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?

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.

• 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). Oct 4, 2018 at 16:44
• @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.) Oct 4, 2018 at 17:35
• Of course, non-free references are also welcome. Oct 5, 2018 at 3:48

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

• 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. Oct 5, 2018 at 9:50
• "it's difficult" -> "it needs another task" Oct 5, 2018 at 10:00
• @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. Oct 5, 2018 at 11:15
• Didn't see @Sam Mcguire's comment above, which gives a clearer picture. Oct 5, 2018 at 11:17
• @Nikhil: Do you know a reference? I also have partial knowledge. Oct 5, 2018 at 12:14