Towards optimal simulations of formulas by bounded-width programs
Richard Cleve · 1990
We show that, over an arbitrary ring, for any fixed e > 0, all balanced algebraic formulas of size s are computed by algebraic straight-line programs that employ a constant number of registers and have length O(sl+C).In particular, in the special case where the ring is GF(2), we obtain a technique for simulating balanced Boolean formulas of size s by bounded-width branching programs of length O(sl+e), for any fixed c > 0. This is an asymptotic improvement in efficiency over previous simulations in both the Boolean and algebraic setting.