BP(f)=O(L(f)1+ε)

Any B₂-formula of size L can be transformed into a branching program of size O(eL^1+ε)for arbitrary E>0. The presented proof is based on a technique due to R. Cleve (1991) to simulate balanced algebraic formulas of size s by algebraic straight-line programs that employ a constant number of registers and have length O(s^1+ε). The best previously known simulation of B2-formulas of size C by branching programs achieves a branching program size of O(L^1.195)