Decision tree approximations of Boolean functions (Q5958322)

Decision trees are popular representations of Boolean functions. We show that, given an alternative representation of a Boolean function \(f,\) say as a read-once branching program, one can find a decision tree \(T\) which approximates \(f\) to any desired amount of accuracy. Moreover, the size of the decision tree is at most that of the smallest decision tree which can represent \(f\) and this construction can be obtained in quasi-polynomial time. We also extend this result to the case where one has access only to a source of random evaluations of the Boolean function \(f\) instead of a complete representation. In this case, we show that a similar approximation can be obtained with any specified amount of confidence (as opposed to the absolute certainty of the former case.) This latter result implies proper PAC-learnability of decision trees under the uniform distribution without using membership queries.