A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
type: Item
instance of: scholarly article
title: A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs
zbMATH Open document ID: 0947.68056
DOI: 10.1016/S0304-3975(98)00219-9
published in: Theoretical Computer Science
publication date: 2000-08-21T00:00:00Z
review text: Branching programs (b.p.'s) or decision diagrams are a general graph-based model of sequential computation. The b.p.'s of polynomial size are a nonuniform counterpart of LOG. Lower bounds for different kinds of restricted b.p.'s are intensively investigated. An important restriction are the so-called \(k\)-b.p.'s, where each computation reads each input variable at most \(k\) times. Although exponential lower bounds have been proven for syntactic \(k\)-b.p.'s, this is not true for general (nonsyntactic) \(k\)-b.p.'s, even for \(k=2\). Therefore, the so-called \((1,+k)\)-b.p.'s are investigated. For some explicit functions, exponential lower bounds for (1,+k)-b.p.'s are known. We prove that the hierarchy of \((1,+k)\)-b.p.'s w.r.t. \(k\) is strict. More exactly, we present (multipointer) functions \(f_{n,k}\) which are polynomially easy for \((1,+k)\)-b.p.'s, but exponentially hard for \((1,+(k-1))\)-b.p.'s for \(k\leqslant \frac 12n^{1/6}/\log^{1/3}n\). This is a generalization of a similar result of \textit{D. Sieling} [J. Comput. Syst. Sci. 53, No.~1, 79-87, Art. No.~0050 (1996; Zbl 0859.68027)] for syntactic \((1,+k)\)-branching programs. As a by-product, we prove a lower bound of \(2^{n-3\sqrt n}\) for an explicit (pointer) function in P.
Mathematics Subject Classification ID: 68Q10
zbMATH DE Number: 1493203
zbMATH Keywords: Boolean functions
zbMATH Keywords: branching programs
zbMATH Keywords: lower bounds
author: Petr Savický
author: Stanislav Zak
MaRDI profile type: Publication
cites work: Randomization and nondeterminism are comparable for ordered read-once branching programs
cites work: The polynomial method and restricted sums of congruence classes
cites work: Q4938624
cites work: A lower bound for read-once-only branching programs
cites work: On lower bounds for read-\(k\)-times branching programs
cites work: On the size of binary decision diagrams representing Boolean functions
cites work: Cyclic Spaces for Grassmann Derivatives and Additive Theory
cites work: Q3694708
cites work: A simple function that requires exponential size read-once branching programs
cites work: Entropy of contact circuits and lower bounds on their complexity
cites work: A note on read-$k$ times branching programs
cites work: Neither reading few bits twice nor reading illegally helps much
cites work: Q3783566
cites work: Q3364203
cites work: Q4234058
cites work: Q3248054
cites work: A lower bound on branching programs reading some bits twice
cites work: New lower bounds and hierarchy results for restricted branching programs
cites work: Q4287364
cites work: On the complexity of branching programs and decision trees for clique functions
cites work: Q3347300
cites work: A superpolynomial lower bound for (1,+k(n))-branching programs
Wikidata QID: Q127725420
description: scientific article; zbMATH DE number 1493203