License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2014.409
URN: urn:nbn:de:0030-drops-44756
URL: https://drops.dagstuhl.de/opus/volltexte/2014/4475/
Go to the corresponding LIPIcs Volume Portal


Iwama, Kazuo ; Nagao, Atsuki

Read-Once Branching Programs for Tree Evaluation Problems

pdf-format:
33.pdf (0.7 MB)


Abstract

Toward the ultimate goal of separating L and P, 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.

BibTeX - Entry

@InProceedings{iwama_et_al:LIPIcs:2014:4475,
  author =	{Kazuo Iwama and Atsuki Nagao},
  title =	{{Read-Once Branching Programs for Tree Evaluation Problems}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{409--420},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4475},
  URN =		{urn:nbn:de:0030-drops-44756},
  doi =		{10.4230/LIPIcs.STACS.2014.409},
  annote =	{Keywords: Lower bounds, Branching Programs, Read-Once Branching Programs, Space Complexity, Combinatorics}
}

Keywords: Lower bounds, Branching Programs, Read-Once Branching Programs, Space Complexity, Combinatorics
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI