Subquadratic Simulations of Balanced Formulae by Branching Programs
Jin‐Yi Cai, Richard J. Lipton · SIAM Journal on Computing · 1994
This paper considers Boolean formulae and their simulations by bounded width branching programs. It is shown that every balanced Boolean formula of size s can be simulated by a constant width (width 5) branching program of length $s^{1.811 \ldots } $. A lower bound for the translational cost from formulae to permutation branching programs is also presented.