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 |