TY - GEN
T1 - Branching programs for tree evaluation
AU - Braverman, Mark
AU - Cook, Stephen
AU - McKenzie, Pierre
AU - Santhanam, Rahul
AU - Wehr, Dustin
PY - 2009
Y1 - 2009
N2 - The problem consists FT h d (k)in computing the value in [k]={1,...,k} taken by the root of a balanced d-ary tree of height h whose internal nodes are labelled with d-ary functions on [k] and whose leaves are labelled with elements of [k]. We propose FT h d (k)as a good candidate for witnessing . We observe that the latter would follow from a proof that k-way branching programs solving FT h d (k)require ω(k unbounded function(h) size. We introduce a "state sequence" method that can match the size lower bounds on obtained by the Nečiporuk method and can yield slightly better (yet still subquadratic) bounds for some nonboolean functions. Both methods yield the tight bounds Θ(k 3) and Θ(k 5/2) for deterministic and nondeterministic branching programs solving respectively. We propose as a challenge to break the quadratic barrier inherent in the Neč iporuk method by adapting the state sequence method to handle FT 4 4.
AB - The problem consists FT h d (k)in computing the value in [k]={1,...,k} taken by the root of a balanced d-ary tree of height h whose internal nodes are labelled with d-ary functions on [k] and whose leaves are labelled with elements of [k]. We propose FT h d (k)as a good candidate for witnessing . We observe that the latter would follow from a proof that k-way branching programs solving FT h d (k)require ω(k unbounded function(h) size. We introduce a "state sequence" method that can match the size lower bounds on obtained by the Nečiporuk method and can yield slightly better (yet still subquadratic) bounds for some nonboolean functions. Both methods yield the tight bounds Θ(k 3) and Θ(k 5/2) for deterministic and nondeterministic branching programs solving respectively. We propose as a challenge to break the quadratic barrier inherent in the Neč iporuk method by adapting the state sequence method to handle FT 4 4.
UR - http://www.scopus.com/inward/record.url?scp=70349338873&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=70349338873&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-03816-7_16
DO - 10.1007/978-3-642-03816-7_16
M3 - Conference contribution
AN - SCOPUS:70349338873
SN - 3642038158
SN - 9783642038150
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 175
EP - 186
BT - Mathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings
T2 - 34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009
Y2 - 24 August 2009 through 28 August 2009
ER -