Subquadratic simulations of circuits by branching programs
Jin‐Yi Cai, R.J. Lipton · 1989
Boolean circuits and their simulations by bounded-width branching programs are considered. It is shown that every NC/sup 1/ circuit of size s can be simulated by a constant-width branching program of length s/sup 1.811. . ./. Some related group-theoretic results are presented.>