<p>Perhaps what you're looking for is theorem 2 in <a href="https://link.springer.com/article/10.1007/BF01200059" rel="nofollow noreferrer">Cleve, R. Towards optimal simulations of formulas by bounded-width programs</a>.</p>
<p>I don't think the precise statement that you're asking about is known (note the size <span class="math-container">$s$</span> could be much less than <span class="math-container">$2^d$</span>).</p>

CC BY-SA 4.0
2023-12-30T11:11:15.107Z
Thanks! This is essentially what I was looking for. I guess my precise statement was a little too ambitious.
Michael Lampis
CC BY-SA 4.0
2023-12-28T19:06:26.577Z
2023-12-31T01:29:27.757Z
2023-12-31T01:29:27.757Z
Ryan Williams
<p>Barrington's theorem states that any Boolean circuit made up of gates of fan-in <span class="math-container">$2$</span> and with depth <span class="math-container">$d$</span> can be transformed into an equivalent Branching Program of constant width (in particular, of width <span class="math-container">$w=5$</span>). The length of the resulting branching program is <span class="math-container">$4^d$</span>.</p>
<p>I am wondering if there are any trade-off versions of this theorem. In particular, is it known if it is possible to decrease the length of the resulting program if we allow the width to become a larger constant?</p>
<p>For example, suppose I have a circuit of depth <span class="math-container">$d$</span> and total size <span class="math-container">$s$</span>. If I allow the width of my branching program to become some constant <span class="math-container">$w&gt;5$</span>, could I hope to obtain a program of length <span class="math-container">$s\cdot 2^{d/f(w)}$</span>, for some function <span class="math-container">$f$</span>?</p>

<cc.complexity-theory><circuit-complexity><circuit-depth>
Trade-off for Barrington's theorem
Michael Lampis
# Trade-off for Barrington's theorem

(Asked by: username_0 on 2023-12-28)

Barrington's theorem states that any Boolean circuit made up of gates of fan-in $2$ and with depth $d$ can be transformed into an equivalent Branching Program of constant width (in particular, of width $w=5$). The length of the resulting branching program is $4^d$.

I am wondering if there are any trade-off versions of this theorem. In particular, is it known if it is possible to decrease the length of the resulting program if we allow the width to become a larger constant?

For example, suppose I have a circuit of depth $d$ and total size $s$. If I allow the width of my branching program to become some constant $w>5$, could I hope to obtain a program of length $s\cdot 2^{d/f(w)}$, for some function $f$?

**Tags:** cc.complexity-theory, circuit-complexity, circuit-depth

---

## 1 answers

### Answer by username_1 on 2023-12-28. Score: 10 | Accepted answer

Perhaps what you're looking for is theorem 2 in [Cleve, R. Towards optimal simulations of formulas by bounded-width programs](https://link.springer.com/article/10.1007/BF01200059).

I don't think the precise statement that you're asking about is known (note the size $s$ could be much less than $2^d$).

> **Comments:**
> **username_0**: Thanks! This is essentially what I was looking for. I guess my precise statement was a little too ambitious.  

---

