Branching programs for tree evaluation

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

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

4 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationMathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings
Number of pages12
StatePublished - 2009
Externally publishedYes
Event34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009 - Novy Smokovec, High Tatras, Slovakia
Duration: Aug 24 2009Aug 28 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5734 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009
CityNovy Smokovec, High Tatras

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Branching programs for tree evaluation'. Together they form a unique fingerprint.

Cite this