### Abstract

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 language | English (US) |
---|---|

Title of host publication | Mathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings |

Pages | 175-186 |

Number of pages | 12 |

DOIs | |

State | Published - Sep 28 2009 |

Externally published | Yes |

Event | 34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009 - Novy Smokovec, High Tatras, Slovakia Duration: Aug 24 2009 → Aug 28 2009 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 5734 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Other

Other | 34th International Symposium on Mathematical Foundations of Computer Science 2009, MFCS 2009 |
---|---|

Country | Slovakia |

City | Novy Smokovec, High Tatras |

Period | 8/24/09 → 8/28/09 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Science(all)

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

## Cite this

*Mathematical Foundations of Computer Science 2009 - 34th International Symposium, MFCS 2009, Proceedings*(pp. 175-186). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5734 LNCS). https://doi.org/10.1007/978-3-642-03816-7_16