Fractional pebbling and thrifty branching programs

Mark Braverman, Stephen Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

We study the branching program complexity of the tree evaluation problem, introduced in [3] 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,⋯,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 [3]. Here we introduce the notion of fractional pebbling of graphs to study non-deterministic branching program size. We prove that this yields non-deterministic branching programs with Θ(k h/2+1) states solving the Boolean problem "determine whether the root has value 1" for binary trees - this is asymptotically better than the branching program size corresponding to black-white pebbling. We prove upper and lower bounds on the fractional pebbling number of d-ary trees, as well as a general result relating the fractional pebbling number of a graph to the black-white pebbling number. We introduce a simple semantic restriction called thrifty on k-way branching programs solving tree evaluation problems and show that the branching program size bound of Θ(kh) is tight (up to a constant factor) for all h ≥ 2 for deterministic thrifty programs. We show that the non-deterministic branching programs that correspond to fractional pebbling are thrifty as well, and that the bound of Θ(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 L from LogCFL and proving it for non-deterministic programs would separate NL from LogCFL.

Original languageEnglish (US)
Title of host publicationFoundations of Software Technology and Theoretical Computer Science, FSTTCS 2009 - 29th Annual Conference, Proceedings
Pages109-120
Number of pages12
DOIs
StatePublished - Dec 1 2009
Externally publishedYes
Event29th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009 - Kanpur, India
Duration: Dec 15 2009Dec 17 2009

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume4
ISSN (Print)1868-8969

Other

Other29th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009
CountryIndia
CityKanpur
Period12/15/0912/17/09

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Fractional pebbling and thrifty branching programs'. Together they form a unique fingerprint.

  • Cite this

    Braverman, M., Cook, S., McKenzie, P., Santhanam, R., & Wehr, D. (2009). Fractional pebbling and thrifty branching programs. In Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2009 - 29th Annual Conference, Proceedings (pp. 109-120). (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 4). https://doi.org/10.4230/LIPIcs.FSTTCS.2009.2311