An improved lower bound for the randomized decision tree complexity of recursive majority.
Nikos LeonardosPublished in: Electron. Colloquium Comput. Complex. (2012)
Keyphrases
- lower bound
- decision trees
- worst case
- upper bound
- randomized algorithms
- np hard
- randomized algorithm
- decision tree induction
- complexity analysis
- branch and bound algorithm
- decision tree classifiers
- optimal solution
- objective function
- decision tree algorithm
- decision forest
- data sets
- polynomial approximation
- decision tree learning
- space complexity
- random forest
- machine learning algorithms