License: 
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2009.2311
URN: urn:nbn:de:0030-drops-23111
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2311/
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 non-deterministicbranching program size. We prove that this yields non-deterministic 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 toblack-white 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 black-white 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 thenon-deterministic branching programs that correspond to fractional pebbling are
thrifty as well, and that the bound of $\Theta(k^{h/2+1})$ is tight for
non-deterministic 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 non-deterministic 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 = {109--120},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-13-2},
ISSN = {1868-8969},
year = {2009},
volume = {4},
editor = {Ravi Kannan and K. Narayan Kumar},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2009/2311},
URN = {urn:nbn:de:0030-drops-23111},
doi = {10.4230/LIPIcs.FSTTCS.2009.2311},
annote = {Keywords: Branching programs, space complexity, tree evaluation, pebbling}
}
|
Keywords: |
|
Branching programs, space complexity, tree evaluation, pebbling |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
|
Issue Date: |
|
2009 |
|
Date of publication: |
|
14.12.2009 |
