## Abstract

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).

[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 language | English |
---|---|

Title of host publication | Mathematical Foundations of Computer Science 2009 |

Subtitle of host publication | 34th International Symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24-28, 2009. Proceedings |

Publisher | Springer Berlin Heidelberg |

Pages | 175-186 |

Number of pages | 12 |

Volume | 5734 |

ISBN (Electronic) | 978-3-642-03816-7 |

ISBN (Print) | 978-3-642-03815-0 |

DOIs | |

Publication status | Published - 2009 |