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$?


1 Answer 1


Perhaps what you're looking for is theorem 2 in Cleve, R. Towards optimal simulations of formulas by bounded-width programs.

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

  • $\begingroup$ Thanks! This is essentially what I was looking for. I guess my precise statement was a little too ambitious. $\endgroup$ Dec 30, 2023 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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