Optimal decision trees and one-time-only branching programs for symmetric Boolean functions

DOI10.1016/S0019-9958(84)80031-5MaRDI QIDQ3722429zbMATH OpenFDO

Authors Ingo Wegener

Publication date 1984

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(84)80031-5

zbMATH Keywords

Combinational complexitydecision tree complexitydepthexponential lower boundone-time-only branching program complexityquadratic lower bound

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 3866582
• Lower bounds to the complexity of symmetric Boolean functions
• scientific article; zbMATH DE number 3913677
• On the combinational complexity of certain symmetric Boolean functions
• Totally optimal decision trees for Boolean functions

Cited in

(16)

• Time-space trade-offs for branching programs
• Separating complexity classes related to -decision trees
• Efficient data structures for Boolean functions
• Optimal ordered binary decision diagrams for read-once formulas
• Coxeter groups and nonuniform complexity
• Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case
• Totally optimal decision trees for Boolean functions
• scientific article; zbMATH DE number 3866582 (Why is no real title available?)
• Lower bounds on the complexity of real-time branching programs
• scientific article; zbMATH DE number 61460 (Why is no real title available?)
• On the relation between BDDs and FDDs (extended abstract)
• Exact OBDD Bounds for Some Fundamental Functions
• Properties of complexity measures for PRAMs and WRAMs
• On the size of binary decision diagrams representing Boolean functions
• Lower bounds to the complexity of symmetric Boolean functions
• The optimal read-once branching program complexity for the direct storage access function

This page was built for publication: Optimal decision trees and one-time-only branching programs for symmetric Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3722429)