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 -