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.

Improve this question
$\endgroup$
  • 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$ – Sam McGuire Oct 4 '18 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$ – Hiroki Morizumi Oct 4 '18 at 17:35
  • $\begingroup$ Of course, non-free references are also welcome. $\endgroup$ – Hiroki Morizumi Oct 5 '18 at 3:48
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.

Improve this answer
$\endgroup$
  • $\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$ – Hiroki Morizumi Oct 5 '18 at 9:50
  • $\begingroup$ "it's difficult" -> "it needs another task" $\endgroup$ – Hiroki Morizumi Oct 5 '18 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 '18 at 11:15
  • $\begingroup$ Didn't see @Sam Mcguire's comment above, which gives a clearer picture. $\endgroup$ – Nikhil Oct 5 '18 at 11:17
  • $\begingroup$ @Nikhil: Do you know a reference? I also have partial knowledge. $\endgroup$ – Hiroki Morizumi Oct 5 '18 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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