Towards Optimal Simulations of Formulas by Bounded-Width Programs
| Title | Towards Optimal Simulations of Formulas by Bounded-Width Programs |
| Publication Type | Technical Report |
| Year of Publication | 1990 |
| Authors | Cleve, R. |
| Other Numbers | 577 |
| Abstract | 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. |
| URL | http://www.icsi.berkeley.edu/pubs/techreports/tr-90-13.pdf |
| Bibliographic Notes | ICSI Technical Report TR-90-013 |
| Abbreviated Authors | R. Cleve |
| ICSI Publication Type | Technical Report |