<p><span class="math-container">$\mathsf{L}/\mathrm{poly}$</span> can be characterized by polynomial size <em>skew</em> circuits. A boolean circuit is called <em>skew</em> 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 <span class="math-container">$\mathsf{L}/\mathrm{poly}$</span>.</p>

<p>A proof of these simulations can e.g. be found in this <a href="https://doi.org/10.1016/j.tcs.2017.03.013" rel="nofollow noreferrer">paper by Balaji, Krebs and Limaye</a>. </p>

CC BY-SA 4.0
2018-10-05T09:50:25.530Z
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.
Hiroki Morizumi
CC BY-SA 4.0
2018-10-05T10:00:00.033Z
"it's difficult" -> "it needs another task"
Hiroki Morizumi
CC BY-SA 4.0
2018-10-05T11:15:48.310Z
@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
CC BY-SA 4.0
2018-10-05T11:17:25.303Z
Didn't see @Sam Mcguire's comment above, which gives a clearer picture.
Nikhil
CC BY-SA 4.0
2018-10-05T12:14:14.650Z
@Nikhil: Do you know a reference? I also have partial knowledge.
Hiroki Morizumi
CC BY-SA 4.0
2018-10-05T08:54:39.540Z
2018-10-08T08:11:40.360Z
2018-10-08T08:11:40.360Z
Jan Johannsen
<p>Branching programs are usually used as a computation model for non-uniform logarithmic space <span class="math-container">$\mathsf{L}/\mathrm{poly}$</span>.
Is there a reference about Boolean circuits corresponding to <span class="math-container">$\mathsf{L}/\mathrm{poly}$</span>?</p>

<p>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 <span class="math-container">$\mathsf{L}/\mathrm{poly}$</span> and Boolean circuits are not used?</p>

<p>[Addition after Sam McGuire's answer (in comments)]</p>

<p>Actually, I'm most interested in Boolean circuits corresponding to <span class="math-container">$\mathsf{L}/\mathrm{quasipoly}$</span>.
I guess that it is quasipolynomial-size <span class="math-container">$O(\log n)$</span>-width Boolean circuits.</p>

<p>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.</p>

CC BY-SA 4.0
2018-10-04T16:44:24.533Z
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_](https://ieeexplore.ieee.org/document/4568025) by Nick Pippenger (I can't find a free .pdf version).
Sam McGuire
CC BY-SA 4.0
2018-10-04T17:35:08.393Z
@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
CC BY-SA 4.0
2018-10-05T03:48:58.867Z
Of course, non-free references are also welcome.
Hiroki Morizumi
<cc.complexity-theory><reference-request><complexity-classes><circuit-complexity><space-bounded>
Boolean circuits which correspond to L/poly
Hiroki Morizumi
# Boolean circuits which correspond to L/poly

(Asked by: username_0 on 2018-10-04)

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.

**Tags:** cc.complexity-theory, reference-request, complexity-classes, circuit-complexity, space-bounded
> **Comments:**
> **username_1**: 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_](https://ieeexplore.ieee.org/document/4568025) by Nick Pippenger (I can't find a free .pdf version).  
> **username_0**: @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.)  
> **username_0**: Of course, non-free references are also welcome.  

---

## 1 answers

### Answer by username_2 on 2018-10-05. Score: 7

$\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](https://doi.org/10.1016/j.tcs.2017.03.013).

> **Comments:**
> **username_0**: 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.  
> **username_0**: "it's difficult" -> "it needs another task"  
> **username_3**: @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.  
> **username_3**: Didn't see @Sam Mcguire's comment above, which gives a clearer picture.  
> **username_0**: @Nikhil: Do you know a reference? I also have partial knowledge.  

---

