A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs

DOI10.1016/S0304-3975(98)00219-9zbMath0947.68056WikidataQ127725420 ScholiaQ127725420MaRDI QIDQ1575258

Stanislav Zak, Petr Savický

Publication date: 21 August 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Boolean functionslower boundsbranching programs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (11)

Bounds on the Fourier coefficients of the weighted sum function ⋮ Reordering method and hierarchies for quantum and classical ordered binary decision diagrams ⋮ A Well-Mixed Function with Circuit Complexity 5n ±o(n): Tightness of the Lachish-Raz-Type Bounds ⋮ On the average sensitivity of the weighted sum function ⋮ Error-Free Affine, Unitary, and Probabilistic OBDDs ⋮ Laced Boolean functions and subset sum problems in finite fields ⋮ The simplified weighted sum function and its average sensitivity ⋮ Complexity Theoretical Results on Nondeterministic Graph-driven Read-Once Branching Programs ⋮ On the relative succinctness of sentential decision diagrams ⋮ A very simple function that requires exponential size read-once branching programs. ⋮ New lower bounds on circuit size of multi-output functions

Cites Work

• A simple function that requires exponential size read-once branching programs
• On the size of binary decision diagrams representing Boolean functions
• A lower bound for read-once-only branching programs
• Entropy of contact circuits and lower bounds on their complexity
• Neither reading few bits twice nor reading illegally helps much
• A lower bound on branching programs reading some bits twice
• New lower bounds and hierarchy results for restricted branching programs
• The polynomial method and restricted sums of congruence classes
• On lower bounds for read-\(k\)-times branching programs
• A superpolynomial lower bound for (1,+k(n))-branching programs
• On the complexity of branching programs and decision trees for clique functions
• Cyclic Spaces for Grassmann Derivatives and Additive Theory
• A note on read-$k$ times branching programs
• Randomization and nondeterminism are comparable for ordered read-once branching programs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A read-once lower bound and a \((1,+k)\)-hierarchy for branching programs