Complexity of Decision Trees for Boolean Functions.
Rusins FreivaldsMasahiro MiyakawaIvo G. RosenbergPublished in: ISMVL (2003)
Keyphrases
- boolean functions
- decision trees
- uniform distribution
- polynomial size
- relevant variables
- dnf formulae
- threshold functions
- functional properties
- disjunctive normal form
- computational complexity
- binary decision diagrams
- membership queries
- bi decomposition
- machine learning
- decision lists
- bounded treewidth
- prime implicants