Branching Programs for Tree Evaluation

Abstract The problem \(FT^{h}_{d}(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 \({FT^{h}_{d}(k)}\) as a good candidate for witnessing \({\mathbf{L}} \subsetneq{\mathbf{LogDCFL}}\). We observe that the latter would follow from a proof that k -way branching programs solving \({FT^{h}_{d}(k)}\) require \(\Omega(k^{\mbox{\scriptsize unbounded function}(h)})\) size. We introduce a “state sequence” method that can match the size lower bounds on \(FT^{h}_{d}(k)\) obtained by the Nec̆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 \(FT^{3}_{2}(k)\) respectively. We propose as a challenge to break the quadratic barrier inherent in the Nec̆iporuk method by adapting the state sequence method to handle \(FT^{4}_{d}(k)\).

Authors

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

Keywords

No keywords are indexed for this paper.