Hierarchy theorems for \(k\)OBDDs and \(k\)IBDDs

DOI10.1016/S0304-3975(97)00034-0zbMath0913.68078OpenAlexW32438244MaRDI QIDQ1275068

Martin Sauerhoff, Ingo Wegener, Detlef Sieling, Beate Bollig

Publication date: 12 January 1999

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00034-0

zbMATH Keywords

lower boundsbinary decision diagramshierarchiescommunication complexitybranching programs

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) General topics in the theory of software (68N01)

Related Items

On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs, Nondeterministic ordered binary decision diagrams with repeated tests and various modes of acceptance, Extension of the hierarchy for \(k\)-OBDDs of small width, Reordering method and hierarchies for quantum and classical ordered binary decision diagrams, On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth, Classical and Quantum Computations with Restricted Memory, BDDs -- design, analysis, complexity, and applications., New size hierarchies for two way automata, Restricted Nondeterministic Read-Once Branching Programs and an Exponential Lower Bound for Integer Multiplication, Satisfiability algorithm for syntactic read-\(k\)-times branching programs, Width hierarchy for \(k\)-OBDD of small width, On the relative succinctness of sentential decision diagrams, Satisfiability Algorithm for Syntactic Read-$k$-times Branching Programs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On oblivious branching programs of linear length
• Lower bounds for depth-restricted branching programs
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• On lower bounds for read-\(k\)-times branching programs
• Graph-Based Algorithms for Boolean Function Manipulation
• On the complexity of branching programs and decision trees for clique functions
• Rounds in Communication Complexity Revisited
• Some bounds on multiparty communication complexity of pointer jumping
• Simultaneous messages vs. communication