# 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). – Sam McGuire Oct 4 '18 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.) – Hiroki Morizumi Oct 4 '18 at 17:35
• Of course, non-free references are also welcome. – Hiroki Morizumi Oct 5 '18 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}$$.
• @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. – Nikhil Oct 5 '18 at 11:15