Towards Optimal Simulations of Formulas by Bounded-Width Programs

TitleTowards Optimal Simulations of Formulas by Bounded-Width Programs
Publication TypeTechnical Report
Year of Publication1990
AuthorsCleve, R.
Other Numbers577

We show that, over an arbitrary ring, for any fixed epsilon > 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 (s superscript(1+epsilon)). 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(s superscript(1+epsilon)), for any fixed epsilon > 0. This is an asymptotic improvement in efficiency over previous simulations in both the Boolean and algebraic setting.

Bibliographic Notes

ICSI Technical Report TR-90-013

Abbreviated Authors

R. Cleve

ICSI Publication Type

Technical Report