Publication Details
Title: Towards Optimal Simulations of Formulas by Bounded-Width Programs
Author: R. Cleve
Group: ICSI Technical Reports
Date: March 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-13.pdf
Overview:
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 Information:
ICSI Technical Report TR-90-013
Bibliographic Reference:
R. Cleve. Towards Optimal Simulations of Formulas by Bounded-Width Programs. ICSI Technical Report TR-90-013, March 1990
Author: R. Cleve
Group: ICSI Technical Reports
Date: March 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-13.pdf
Overview:
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 Information:
ICSI Technical Report TR-90-013
Bibliographic Reference:
R. Cleve. Towards Optimal Simulations of Formulas by Bounded-Width Programs. ICSI Technical Report TR-90-013, March 1990