Lower bounds for depth-restricted branching programs

DOI10.1016/0890-5401(91)90072-AzbMath0800.68495OpenAlexW1963927532MaRDI QIDQ1173954

Matthias Krause

Publication date: 25 June 1992

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0890-5401(91)90072-a

zbMATH Keywords

lower boundscommunication complexitybranching programscomplexity of branching programs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (11)

Communication Complexity and Lower Bounds on Multilective Computations ⋮ Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance ⋮ On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth ⋮ Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines ⋮ Guess-and-verify versus unrestricted nondeterminism for OBDDs and one-way Turing machines. ⋮ On the size of binary decision diagrams representing Boolean functions ⋮ New lower bounds and hierarchy results for restricted branching programs ⋮ Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs ⋮ The nonapproximability of OBDD minimization ⋮ On the nonapproximability of Boolean functions by OBDDs and read-\(k\)-times branching programs ⋮ On oblivious branching programs of linear length

Cites Work

• A Boolean function requiring 3n network size
• Lower bounds on monotone complexity of the logical permanent
• The monotone circuit complexity of Boolean functions
• On the complexity of branching programs and decision trees for clique functions
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Lower bounds for depth-restricted branching programs