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

DOI10.1016/S0019-9958(84)80031-5zbMath0592.94025MaRDI QIDQ3722429

Ingo Wegener

Publication date: 1984

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

zbMATH Keywords

depthexponential lower bounddecision tree complexityquadratic lower boundCombinational complexityone-time-only branching program complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

Time-space trade-offs for branching programs ⋮ Efficient data structures for Boolean functions ⋮ Lower bounds on the complexity of real-time branching programs ⋮ On the size of binary decision diagrams representing Boolean functions ⋮ Separating complexity classes related to \(\Omega\)-decision trees ⋮ The optimal read-once branching program complexity for the direct storage access function ⋮ Competitive Boolean function evaluation: beyond monotonicity, and the symmetric case ⋮ Properties of complexity measures for PRAMs and WRAMs ⋮ Exact OBDD Bounds for Some Fundamental Functions ⋮ Unnamed Item ⋮ Coxeter groups and nonuniform complexity ⋮ Optimal ordered binary decision diagrams for read-once formulas ⋮ On the relation between BDDs and FDDs