Braverman, Mark ;
Cook, Stephen ;
McKenzie, Pierre ;
Santhanam, Rahul ;
Wehr, Dustin
Fractional Pebbling and Thrifty Branching Programs
Abstract
We study the branching program complexity of the {\em tree evaluation problem},
introduced in \cite{BrCoMcSaWe09} as a candidate for separating \nl\ from\logcfl. The input to the problem is a rooted, balanced $d$ary tree of height$h$, whose internal nodes are labelled with $d$ary functions on$[k]=\{1,\ldots,k\}$, and whose leaves are labelled with elements of $[k]$.Each node obtains a value in $[k]$ equal to its $d$ary function applied to the values of its $d$ children. The output is the value of the root.
Deterministic $k$way branching programs as related to black pebbling algorithms have been studied in \cite{BrCoMcSaWe09}. Here we introduce the notion of {\em fractional pebbling} of graphs to study nondeterministicbranching program size. We prove that this yields nondeterministic branching
programs with $\Theta(k^{h/2+1})$ states solving the Boolean problem ``determine whether the root has value 1'' for binary trees  this isasymptotically better than the branching program size corresponding toblackwhite pebbling. We prove upper and lower bounds on the fractionalpebbling number of $d$ary trees, as well as a general result relating thefractional pebbling number of a graph to the blackwhite pebbling number.
We introduce a simple semantic restriction called {\em thrifty} on $k$way branching programs solving tree evaluation problems and show that the branchingprogram size bound of $\Theta(k^h)$ is tight (up to a constant factor) for all
$h\ge 2$ for deterministic thrifty programs. We show that thenondeterministic branching programs that correspond to fractional pebbling are
thrifty as well, and that the bound of $\Theta(k^{h/2+1})$ is tight for
nondeterministic thrifty programs for $h=2,3,4$. We hypothesise that thrifty
branching programs are optimal among $k$way branching programs solving the
tree evaluation problem  proving this for deterministic programs would
separate \lspace\ from \logcfl\, and proving it for nondeterministic programs
would separate \nl\ from \logcfl.
BibTeX  Entry
@InProceedings{braverman_et_al:LIPIcs:2009:2311,
author = {Mark Braverman and Stephen Cook and Pierre McKenzie and Rahul Santhanam and Dustin Wehr},
title = {{Fractional Pebbling and Thrifty Branching Programs}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {109120},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897132},
ISSN = {18688969},
year = {2009},
volume = {4},
editor = {Ravi Kannan and K. Narayan Kumar},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2311},
URN = {urn:nbn:de:0030drops23111},
doi = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2009.2311},
annote = {Keywords: Branching programs, space complexity, tree evaluation, pebbling}
}
Keywords: 

Branching programs, space complexity, tree evaluation, pebbling 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science

Issue date: 

2009 
Date of publication: 

14.12.2009 