English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We study restricted computation models related to the Tree EvaluationProblem}. The TEP was introduced in earlier work as a simple candidate for the(*very*) long term goal of separating L and LogDCFL. The input to the problemis a rooted, balanced binary tree of height h, whose internal nodes are labeledwith binary functions on [k] = {1,...,k} (each given simply as a list of k^2elements of [k]), and whose leaves are labeled with elements of [k]. Each nodeobtains a value in [k] equal to its binary function applied to the values ofits children, and the output is the value of the root. The first restrictedcomputation model, called Fractional Pebbling, is a generalization of theblack/white pebbling game on graphs, and arises in a natural way from thesearch for good upper bounds on the size of nondeterministic branching programs(BPs) solving the TEP - for any fixed h, if the binary tree of height h hasfractional pebbling cost at most p, then there are nondeterministic BPs of sizeO(k^p) solving the height h TEP. We prove a lower bound on the fractionalpebbling cost of d-ary trees that is tight to within an additive constant foreach fixed d. The second restricted computation model we study is a semanticrestriction on (non)deterministic BPs solving the TEP - Thrifty BPs.Deterministic (resp. nondeterministic) thrifty BPs suffice to implement thebest known algorithms for the TEP, based on black (resp. fractional) pebbling.In earlier work, for each fixed h a lower bound on the size of deterministicthrifty BPs was proved that is tight for sufficiently large k. We give analternative proof that achieves the same bound for all k. We show the samebound still holds in a less-restricted model, and also that gradually weakerlower bounds can be obtained for gradually weaker restrictions on the model.

Pebbling and Branching Programs Solving the Tree Evaluation Problem