mlsanityData to 7 Oct 2026

On the Computational Intelligibility of Boolean Classifiers

arXiv 2104.06172 ↗First posted 13 Apr 2021cs.AIcited by 40

Not on the map. Why?

Abstract (arXiv)

In this paper, we investigate the computational intelligibility of Boolean classifiers, characterized by their ability to answer XAI queries in polynomial time. The classifiers under consideration are decision trees, DNF formulae, decision lists, decision rules, tree ensembles, and Boolean neural nets. Using 9 XAI queries, including both explanation queries and verification queries, we show the existence of large intelligibility gap between the families of classifiers. On the one hand, all the 9 XAI queries are tractable for decision trees. On the other hand, none of them is tractable for DNF formulae, decision lists, random forests, boosted decision trees, Boolean multilayer perceptrons, and binarized neural networks.

Key facts. Cited by 40 papers in the map (data through 7 Oct 2026). Builds on 17 of its 50 references that are in the map. First posted on arXiv 13 Apr 2021.

Builds on

17 of 50 references.

References · 17

  1. 2016The Mythos of Model Interpretabilitycited by 716
  2. 2016European Union regulations on algorithmic decision-making and a "right to explanation"cited by 343
  3. 2018Abduction-Based Explanations for Machine Learning Modelscited by 159
  4. 2018A Symbolic Approach to Explaining Bayesian Network Classifierscited by 130
  5. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  6. 2020On The Reasons Behind Decisionscited by 99
  7. 2020On the Tractability of SHAP Explanationscited by 92
  8. 2018Model Agnostic Supervised Local Explanationscited by 83
  9. 2017Verifying Properties of Binarized Deep Neural Networkscited by 77
  10. 2020Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delaycited by 56
  11. 2020On Explaining Decision Treescited by 49
  12. 2019Robustness Verification of Tree-based Modelscited by 33
5 more
  1. 2020Efficient Exact Verification of Binarized Neural Networkscited by 33
  2. 2020Model Agnostic Multilevel Explanationscited by 24
  3. 2019Significance Tests for Neural Networkscited by 17
  4. 2020Learning outside the Black-Box: The pursuit of interpretable modelscited by 17
  5. 2018Logical Explanations for Deep Relational Machines Using Relevance Informationcited by 9

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 6; 2022: 10; 2023: 7; 2024: 3; 2025: 8; 2026: 6.

40 papers.

Sort:

  1. 2022Logic-Based Explainability in Machine Learningcited by 47
  2. 2022On Tackling Explanation Redundancy in Decision Treescited by 44
  3. 2021Explanations for Monotonic Classifierscited by 39
  4. 2021On Efficiently Explaining Graph-Based Classifierscited by 37
  5. 2022On Computing Probabilistic Explanations for Decision Treescited by 35
  6. 2021Trading Complexity for Sparsity in Random Forest Explanationscited by 32
  7. 2023The Inadequacy of Shapley Values for Explainabilitycited by 30
  8. 2022Computing Abductive Explanations for Boosted Treescited by 23
  9. 2023Logic for Explainable AIcited by 23
  10. 2024Local vs. Global Interpretability: A Computational Complexity Perspectivecited by 23
  11. 2022Feature Necessity & Relevancy in ML Classifier Explanationscited by 22
  12. 2024Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementationcited by 20
28 more
  1. 2022On Computing Probabilistic Abductive Explanationscited by 18
  2. 2023Delivering Inflated Explanationscited by 16
  3. 2021A unified logical framework for explanations in classifier systemscited by 15
  4. 2023From Robustness to Explainability and Back Againcited by 14
  5. 2021Efficient Explanations With Relevant Setscited by 12
  6. 2023Disproving XAI Myths with Formal Methods -- Initial Resultscited by 12
  7. 2025Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasonscited by 11
  8. 2026Formal Mechanistic Interpretability: Automated Circuit Discovery with Provable Guaranteescited by 10
  9. 2021Efficient Explanations for Knowledge Compilation Languagescited by 9
  10. 2022Provably Precise, Succinct and Efficient Explanations for Decision Treescited by 8
  11. 2022Modelling and Explaining Legal Case-based Reasoners through Classifierscited by 3
  12. 2025Additive Models Explained: A Computational Complexity Approachcited by 3
  13. 2022On Deciding Feature Membership in Explanations of SDD & Related Classifierscited by 2
  14. 2023Short Boolean Formulas as Explanations in Practicecited by 2
  15. 2024Logic-Based Explainability: Past, Present & Futurecited by 2
  16. 2025Uncovering Bugs in Formal Explainers: A Case Study with PyXAIcited by 1
  17. 2026Provably Explaining Neural Additive Modelscited by 1
  18. 2026Unifying Formal Explanations: A Complexity-Theoretic Perspectivecited by 1
  19. 2022Rectifying Mono-Label Boolean Classifierscited by 0
  20. 2023On Logic-Based Explainability with Partially Specified Inputscited by 0
  21. 2025Interpretable DNFscited by 0
  22. 2025Efficient & Correct Predictive Equivalence for Decision Treescited by 0
  23. 2025User Profiles of Sleep Disorder Sufferers: Towards Explainable Clustering and Differential Variable Analysiscited by 0
  24. 2025A Rectification-Based Approach for Distilling Boosted Trees into Decision Treescited by 0
  25. 2025Leveraging Association Rules for Better Predictions and Better Explanationscited by 0
  26. 2026Fairness of Classifiers in the Presence of Constraints between Featurescited by 0
  27. 2026Dsat: A Native SAT Solver for Discrete Logiccited by 0
  28. 2026Solving Hard XAI Queries Based on a Compiled Dual-Rail Encodingcited by 0