Branching Programs for Tree Evaluation

Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

The problem F T hd (k) consists 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 F T h d (k) as a good candidate for witnessing L LogDCFL. We observe that the latter would follow from a proof that k-way branching programs solving F T hd (k) require Ω(kunbounded function(h) ) size. We introduce a “state
sequence” method that can match the size lower bounds on F T hd (k) obtained by the Ne˘ciporuk method and can yield slightly better (yet still subquadratic) bounds for some nonboolean functions. Both methods yield the tight bounds Θ(k3) and Θ(k5/2) for deterministic and nondeterministic
branching programs solving F T 3 2 (k) respectively. We propose as a challenge to break the quadratic barrier inherent in the Ne˘ciporuk method by adapting the state sequence method to handle F T 4 d (k).
Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2009
Subtitle of host publication34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings
PublisherSpringer Berlin Heidelberg
Number of pages12
ISBN (Electronic)978-3-642-03816-7
ISBN (Print)978-3-642-03815-0
Publication statusPublished - 2009


Dive into the research topics of 'Branching Programs for Tree Evaluation'. Together they form a unique fingerprint.

Cite this