Totally optimal decision trees for Boolean functions

Igor Chikalov, Shahid Hussain, Mikhail Moshkov

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


We study decision trees which are totally optimal relative to different sets of complexity parameters for Boolean functions. A totally optimal tree is an optimal tree relative to each parameter from the set simultaneously. We consider the parameters characterizing both time (in the worst- and average-case) and space complexity of decision trees, i.e., depth, total path length (average depth), and number of nodes. We have created tools based on extensions of dynamic programming to study totally optimal trees. These tools are applicable to both exact and approximate decision trees, and allow us to make multi-stage optimization of decision trees relative to different parameters and to count the number of optimal trees. Based on the experimental results we have formulated the following hypotheses (and subsequently proved): for almost all Boolean functions there exist totally optimal decision trees (i) relative to the depth and number of nodes, and (ii) relative to the depth and average depth.
Original languageEnglish (US)
Pages (from-to)1-13
Number of pages13
JournalDiscrete Applied Mathematics
StatePublished - Jul 28 2016

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: Research reported in this publication was supported by the King Abdullah University of Science and Technology (KAUST). Authors acknowledge valuable comments and suggestions by anonymous reviewers that clearly improved the readability of this work and helped prove the two hypotheses.


Dive into the research topics of 'Totally optimal decision trees for Boolean functions'. Together they form a unique fingerprint.

Cite this