 Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Mittagsseminar (in cooperation with M. Ghaffari, A. Steger and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Tuesday, December 16, 2014, 12:15 pm

Duration: 30 minutes

Location: CAB G51

Speaker: Kazuo Iwama (Kyoto University)

Read-Once Branching Programs for Tree Evaluation Problems

Toward the ultimate goal of separating L (Log Space) and P (Poly Time), Cook, McKenzie, Wehr, Braverman and Santhanam introduced the "tree evaluation problem" (TEP). For fixed $h,k > 0$, $FT_h(k)$ is given as a complete, rooted binary tree of height $h$, in which each internal node is associated with a function from $[k]^2$ to $[k]$, and each leaf node with a number in $[k]$. The value of an internal node $v$ is defined naturally, i.e., if it has a function $f$ and the values of its two child nodes are a and b, then the value of $v$ is $f(a,b)$. Our task is to compute the value of the root node by sequentially executing this function evaluation in a bottom-up fashion. The problem is obviously in P and if we could prove that any branching program solving $FT_h(k)$ needs at least $k^{r(h)}$ states for any unbounded function $r$, then this problem is not in L, thus achieving our goal. The above authors introduced a restriction called "thrifty" against the structure of BP's (i,e., against the algorithm for solving the problem) and proved that any thrifty BP needs $\Omega(k^h)$ states. This paper proves a similar lower bound for "read-once" branching programs, which allows us to get rid of the restriction on the order of nodes read by the BP that is the nature of the thrifty restriction.

This is a joint work with Atsuki Nagao.

Upcoming talks     |     All previous talks     |     Talks by speaker     | Upcoming talks in iCal format (beta version!)

Information for students and suggested topics for student talks