Pith. sign in

REVIEW 3 major objections 3 minor 96 references

What makes an Ensemble (Un) Interpretable?

T0 review · 3 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Ensemble interpretability is governed by the number and type of base models, not their size: fixed-count tree ensembles are explainable in polynomial time, while two linear models already make explanation queries intractable.

desk verdict A useful complexity map for ensemble interpretability, but the load-bearing MSR gadget in Appendix F is false, so the headline SigmaP2-hardness results need repair. read the letter →

arxiv 2506.08216 v1 pith:4LC4Q7OM submitted 2025-06-09 cs.LG cs.CCcs.LO

Shahaf Bassan , Guy Amir , Meirav Zehavi , Guy Katz This is my paper
classification cs.LGcs.CCcs.LO MSC 68Q1768Q27
keywords ensembleinterpretabilitycomputationalcomplexityparameterizedsufficientreasoncontrastiveexplanationShapleyvaluesdecisiontreeensembleslinearmodel
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to establish that the folklore switch from “a single model is interpretable” to “an ensemble is a black box” has a precise complexity-theoretic signature. It claims that under standard assumptions ($\mathrm{P} \neq \mathrm{NP}$ and $\mathrm{FPT} \neq W[1]$), the number of base models and their type matter more than their size: ensembles of even constant-size linear models, decision trees, or neural networks remain intractable to explain, while an ensemble of a fixed number of decision trees becomes polynomial-time explainable for four of the five queries studied. The paper additionally claims strict computational gaps: decision-tree ensembles are strictly more c-interpretable than linear-model ensembles for all five explanation forms, and ensembles of linear models are hard already at two members. If correct, this provides the first complete parameterized complexity map for these five explanation queries, and it gives practitioners a concrete architectural rule: fewer but deeper trees beat many shallow ones, whereas adding even a couple of linear models destroys tractable explainability.

What carries the argument

The load-bearing construction is the reduction of Boolean formulas to ensembles whose base models are “poly-subset-constructable”: a family where, given any partial assignment $x_S$, one can build in polynomial time a base model that returns 1 exactly on inputs agreeing with $x_S$. The paper shows decision trees and perceptrons are such families, so every DNF becomes an equivalent majority-voting ensemble of $O(n)$ small base models, and this conversion preserves the difficulty of sufficient-reason, contrastive-reason, counting, and Shapley queries. The hardest MSR results reduce from Shortest-Implicant-Core (for general ensembles) and from a constrained Generalized Subset-Sum problem (for five perceptrons). FPT reductions to and from $k$-Clique and counting $k$-Clique carry the tree-ensemble tractability results, and the property “closed under ensemble construction” explains why neural networks show no complexity gap.

What would settle it

Examine the reducibility of Shortest-Implicant-Core with constant-size DNF terms: if that restricted problem is shown not to be $\Sigma^P_2$-hard (for example, by a polynomial-time algorithm or by a reduction that only proves NP-hardness), then the paper's MSR classifications for ensembles of decision trees and linear models collapse.

Watch

Extended reading notes

Core claim

The central discovery is that explainability of ensembles is not governed by base-model size but by base-model count and type. The paper proves that for ensembles of decision trees and of linear classifiers, checking a sufficient reason is $\mathrm{coNP}$-complete, finding a minimum contrastive reason is $\mathrm{NP}$-complete, finding a minimum sufficient reason is $\Sigma^P_2$-complete, counting completions is $\#\mathrm{P}$-complete, and computing Shapley values is $\#\mathrm{P}$-hard, while the corresponding single-model queries are mostly polynomial-time. Parameterized by the largest base model, all five queries are para-$\mathrm{coNP}$, para-$\mathrm{NP}$, para-$\Sigma^P_2$, or para-$\#\mathrm{P}$ complete or hard already at constant size. Parameterized by number of base models, the contrast is sharp: $k$-ensembles of linear models are para-$\mathrm{coNP}$, para-$\mathrm{NP}$, para-$\Sigma^P_2$, or para-$\#\mathrm{P}$ complete or hard (CSR and MCR already for $k=2$, MSR for $k=5$), whereas $k$-ensembles of decision trees are $\mathrm{co}W[1]$-complete, $W[1]$-hard, $\#W[1]$-complete, or in XP/XNP, hence polynomial-time for fixed $k$. For neural networks the ensemble construction adds no complexity, because any ReLU network ensemble can be collapsed into a single network in polynomial time.

Load-bearing premise

The strongest new hardness results for Minimum Sufficient Reason rest on a lemma, imported from earlier work, that Shortest-Implicant-Core stays $\Sigma^P_2$-hard even when DNF terms have constant size, plus a sketched refinement of the DNF; if either step fails, the MSR classifications weaken.

Editorial extensions

If this is right

  • For a fixed number of decision trees, CSR, MCR, CC, and SHAP become polynomial-time solvable; with constant leaf count per tree, they become fixed-parameter tractable even for arbitrarily large trees.
  • Any ensemble containing two linear models is already intractable to explain for all five query forms, so mixing a few linear models into a heterogeneous ensemble destroys tractable explainability.
  • Shrinking base models to constant size does not restore interpretability: all five queries remain intractable under maximal-base-model-size parameterization.
  • Neural-network ensembles gain no extra hardness from aggregation, because an ensemble of ReLU networks is reducible to a single ReLU network.
  • Tree ensembles are strictly more c-interpretable than linear-model ensembles with respect to CSR, MSR, MCR, CC, and SHAP.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same complexity map suggests that practical explanation tools for tree ensembles should fix the tree count and bound leaf counts, since the paper's FPT bounds grow as $O(m^k)$; this is an editorial extrapolation of its runtime statement.
  • Because the reductions use only majority and weighted voting, the para-hardness for two linear models likely transfers to stacking ensembles whose meta-learner can implement a threshold vote, a consequence the paper only notes in passing.
  • A testable extension is to parameterize by the total number of leaves or the ensemble's global size instead of per-tree leaf count; the paper's XP algorithms suggest those parameters may be smaller than $k$, but this is not established.
  • The query-dependent complexity gaps imply that “interpretable ensemble” should be qualified by explanation type: a model can be tractable for sufficient reasons yet intractable for Shapley values, so empirical benchmarks should report query-specific behavior.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 3 minor

Summary. The paper studies the computational interpretability of ensemble classifiers through complexity theory. It analyzes five explanation queries (CSR, MCR, MSR, CC, and SHAP) over ensembles whose base models are decision trees, perceptrons/linear models, or ReLU networks, under majority and weighted voting, and in both classical and parameterized settings. The headline claims are that ensembles remain intractable even with constant-size base models; that the number of base models matters sharply, with fixed-k tree ensembles being XP/W-hierarchy tractable while constant-size linear-model ensembles are para-intractable; and that neural networks are closed under ensemble construction. The technical centerpiece is a claimed corrected proof that MSR on tree/linear ensembles is ΣP2-hard, together with several para-ΣP2 and para-#P classifications. Full proofs are relegated to the appendices.

Significance. If the results were correct, the paper would provide the first complete parameterized complexity map for these five explanation queries across three base-model families, with direct practical implications for random forests, XGBoost, and linear-model ensembles. The manuscript is commendably explicit about reductions and honestly identifies a technical gap in prior work on MSR hardness. However, the central MSR-hardness proof contains a false lemma, and the affected classifications are unsupported as written. The five-perceptron MSR reduction via generalized subset sum appears independent and may be salvageable, but the tree-ensemble and constant-size-base-model MSR results require either a new correct reduction or a weakening of the claims.

major comments (3)
  1. [Appendix F, Claim 2 (Eq. (23))] Claim 2 is false as stated. Take φ = (x1x3) ∨ (x2¬x3) ∨ (x1x2), with tn = x1x2 and all non-target terms of size 2. For t1 = x1x3 we have r1 = {x3}; the subset S = {t2} covers both assignments of x3 (x3 = 1 via t1 and x3 = 0 via t2), so the construction adds the term ¬x3. Symmetrically, for t2 = x2¬x3 the subset S = {t1} adds the term x3. Hence φ'' = x1x2 ∨ x3 ∨ ¬x3, which is a tautology. The singleton C = {x1} ⊆ tn is then an implicant of φ'', but C is not an implicant of φ because the assignment x1 = 1, x2 = 0, x3 = 0 falsifies φ. This directly contradicts the 'if and only if' in Claim 2, and the counterexample lies exactly in the constant-size term regime (d = 2), so the constant-DNF restriction does not repair the lemma.
  2. [Appendix F, concluding reduction; Propositions 4.2(iii), 5.1(iii)] The ΣP2-hardness of MSR for DNF-representable ensembles rests on the false Claim 2. The concluding step of Appendix F asserts that an implicant C ⊆ tn of φ'' of size k exists iff a sufficient reason of size k exists for ⟨f, x⟩, and that assertion is precisely where the faulty elimination of non-tn variables is used. Consequently, Proposition 4.2(iii), the corresponding entries in Tables 1 and 2, and the MSR separations in Theorems 4.3 and 5.7 are unsupported as written. The paper must either supply a correct reduction from Shortest-Implicant-Core to MSR for these ensemble classes or explicitly weaken these claims.
  3. [Appendix I (proof of Proposition 5.1)] The proof of Proposition 5.1 is incomplete: the text breaks off at 'For the CC query.' before giving the CC-hardness reduction, and the MSR paragraph cites Dick et al. (2009) without showing how a constant-term SIC instance is encoded into an ensemble of constant-size base models while preventing variables outside tn from appearing in sufficient reasons. Since the only mechanism offered for that prevention is the false Claim 2, Proposition 5.1(iii) is not established by the current text. In addition, Claim 1 (Shortest-Implicant-Core for constant-size DNF terms is ΣP2-hard) is only asserted to follow from Umans (2001); a precise derivation or a precise pointer is needed because the constant-size restriction is essential to the reduction.
minor comments (3)
  1. [Section 5.1 and Appendix I/J] The appendix references are inconsistent: the proof sketch for Proposition 5.1 says 'The proof appears in Appendix J', then a later sentence says 'The proof of Proposition 5.1 appears in Appendix I'. Please correct the cross-references.
  2. [Appendix J, Claim 10] The five-perceptron MSR proof contains variable slips and an unresolved placeholder: f5 is defined as the indicator of the input 1n, but later text says 'f3 is an indicator for the input 1n'; the construction of f5 is deferred with 'as demonstrated in (?)' and no reference or proof is supplied. These issues should be fixed so the reduction can be checked.
  3. [Throughout] There are numerous typographical errors, e.g., 'paramaterized', 'hirerchy', 'seperattley', 'furmula', and 'tbe'. They do not affect the mathematics but should be cleaned up in revision.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the ensemble complexity results are derived by standard reductions from external complete problems, not from the paper's own targets.

full rationale

This is a pure complexity-theory paper: every central claim is a completeness or hardness classification obtained by polynomial or FPT reductions from established external problems, such as Umans (2001) Shortest-Implicant-Core, Schaefer and Umans (2002) GSSP, Valiant (1979) DNF model counting, Barceló et al. (2020) MLP MSR, and Ordyniak et al. (2024) tree-ensemble parameterized results. No parameter is fitted to data, and no quantity is defined in terms of the quantity it is claimed to derive, so the self-definitional and fitted-input-called-prediction patterns are absent. The self-citations that occur, such as Amir et al. (2024) for polynomial-time negation of decision trees, perceptrons, and MLPs, are not load-bearing in a circular sense: the negation fact is elementary, is effectively re-proved in Lemma F.9, and its statement does not include the ensemble-hardness conclusions of this paper. The genuine vulnerabilities are mathematical-rigor issues, not circularity: Appendix F's Claim 1 asserts that Shortest-Implicant-Core remains SigmaP2-hard for constant-size terms by saying the proof directly follows from Umans (2001), and Claim 2's phi'' construction is only sketched; the attached skeptic note disputes whether those steps are correct. If the phi'' gadget is false, then Propositions 4.2(iii), 5.1(iii), and 5.2(iii) would be unsupported as written, but that is a correctness failure, not an equivalence between output and input by construction. There is no self-citation chain that forces the conclusions, no uniqueness theorem imported from the authors' own prior work, and no ansatz smuggled in via a self-citation. The hardness anchors are reductions from problems outside the paper, and the membership arguments are constructive algorithms, so the derivation chain is self-contained against external benchmarks. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters or invented entities. The analysis relies on standard complexity conjectures, known complete-problem reductions, and explicit modeling assumptions including Boolean domain, product distributions, and voting rules. The most fragile imported fact is the unproven-in-paper constant-DNF Shortest-Implicant-Core hardness lemma.

assumptions (4)
  • domain assumption P not equal to NP and standard parameterized separations such as FPT not equal to W[1]
    Used throughout to turn hardness into strictly less interpretable, as in Definition 4.1, Theorem 4.3, and Theorem 5.7. Without these conjectures, the negative results are conditional.
  • standard math Shortest-Implicant-Core for constant-size-term DNFs is SigmaP2-hard
    Invoked in Appendix F, Claim 1. The paper does not reproduce the proof and attributes it to Umans 2001. Load-bearing for MSR hardness in Propositions 4.2, 5.1, and 5.2.
  • domain assumption Feature independence, equivalently product distributions, for CC and SHAP
    Assumed in Section 3.2 and Appendix D. Matches KernelSHAP, but the complexity results for SHAP may not transfer to dependent feature distributions.
  • domain assumption Boolean input domains as the formal setting, with extension claims for continuous inputs and regression
    Main definitions in Section 2 set F = {0,1}^n. Appendix E claims extensions to discrete or real inputs and regression without complete proofs for every query.

how reviews work

0 comments
Cite this review

Pith. "Pith review of What makes an Ensemble (Un) Interpretable?." pith.science (2026). https://pith.science/paper/4LC4Q7OM

@misc{pith2026250608216,
  author       = {Pith},
  title        = {Pith review of: What makes an Ensemble (Un) Interpretable?},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4LC4Q7OM}},
  note         = {Machine review of arXiv:2506.08216}
}
abstract

Ensemble models are widely recognized in the ML community for their limited interpretability. For instance, while a single decision tree is considered interpretable, ensembles of trees (e.g., boosted trees) are often treated as black-boxes. Despite this folklore recognition, there remains a lack of rigorous mathematical understanding of what particularly makes an ensemble (un)-interpretable, including how fundamental factors like the (1) *number*, (2) *size*, and (3) *type* of base models influence its interpretability. In this work, we seek to bridge this gap by applying concepts from computational complexity theory to study the challenges of generating explanations for various ensemble configurations. Our analysis uncovers nuanced complexity patterns influenced by various factors. For example, we demonstrate that under standard complexity assumptions like P$\neq$NP, interpreting ensembles remains intractable even when base models are of constant size. Surprisingly, the complexity changes drastically with the number of base models: small ensembles of decision trees are efficiently interpretable, whereas interpreting ensembles with even a constant number of linear models remains intractable. We believe that our findings provide a more robust foundation for understanding the interpretability of ensembles, emphasizing the benefits of examining it through a computational complexity lens.

Figures

Figures reproduced from arXiv: 2506.08216 by the authors.

Figure 1
Figure 1. Illustration of insights from our parameterized complexity results: even highly simplified ensembles with constant-size base models (e.g., three base models) remain intractable to interpret. Moreover, ensembles with just two linear models already pose intractability, highlighting the substantial difficulty of interpreting linear model ensembles, even in simplified cases. However, reducing the number of trees in tree… view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

96 extracted references · 73 canonical work pages

  1. [1]

    The Computational Complexity of Circuit Discovery for Inner Interpretability

    Adolfi, F., Vilas, M., and Wareham, T. The Computational Complexity of Circuit Discovery for Inner Interpretability . In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025

    2025

  2. [2]

    and Jaakkola, T

    Alvarez Melis, D. and Jaakkola, T. Towards Robust Interpretability with Self-Explaining Neural Networks . In Proc. 31st Int. Conf. on Advances in neural information processing systems (Neurips), 2018

    2018

  3. [3]

    Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation

    Amir, G., Bassan, S., and Katz, G. Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation . In Proc. 27th European Conf. on Artifical Intelligence (ECAI), 2024

    2024

  4. [4]

    Foundations of Symbolic Languages for Model Interpretability

    Arenas, M., Baez, D., Barcel \'o , P., P \'e rez, J., and Subercaseaux, B. Foundations of Symbolic Languages for Model Interpretability . Proc. 34th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp.\ 11690--11701, 2021 a

    2021

  5. [5]

    The Tractability of SHAP-Score-Based Explanations for Classification Over Deterministic and Decomposable Boolean Circuits

    Arenas, M., Barcel \'o , P., Bertossi, L., and Monet, M. The Tractability of SHAP-Score-Based Explanations for Classification Over Deterministic and Decomposable Boolean Circuits . In Proc. 35th AAAI Conf. on Artificial Intelligence, pp.\ 6670--6678, 2021 b

    2021

  6. [6]

    On Computing Probabilistic Explanations for Decision Trees

    Arenas, M., Barcel \'o , P., Romero, M., and Subercaseaux, B. On Computing Probabilistic Explanations for Decision Trees . Proc. 35th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp.\ 28695--28707, 2022

    2022

  7. [7]

    On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results

    Arenas, M., Barcel \'o , P., Bertossi, L., and Monet, M. On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results . Journal of Machine Learning Research (JMLR), 24 0 (63): 0 1--58, 2023

    2023

  8. [8]

    and Barak, B

    Arora, S. and Barak, B. Computational Complexity: A Modern Approach . Cambridge University Press, 2009

    2009

Show all 96 references
  1. [9]

    On Preferred Abductive Explanations for Decision Trees and Random Forests

    Audemard, G., Bellart, S., Bounia, L., Koriche, F., Lagniez, J.-M., and Marquis, P. On Preferred Abductive Explanations for Decision Trees and Random Forests . In Proc. 31st Int. Joint Conf. on Artificial Intelligence (IJCAI), pp.\ 643--650, 2022 a

    2022

  2. [10]

    Trading Complexity for Sparsity in Random Forest Explanations

    Audemard, G., Bellart, S., Bounia, L., Koriche, F., Lagniez, J.-M., and Marquis, P. Trading Complexity for Sparsity in Random Forest Explanations . In Proc. 36th AAAI Conf. on Artificial Intelligence, pp.\ 5461--5469, 2022 b

    2022

  3. [11]

    Computing Abductive Explanations for Boosted Trees

    Audemard, G., Lagniez, J.-M., Marquis, P., and Szczepanski, N. Computing Abductive Explanations for Boosted Trees . In Proc. 26th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pp.\ 4699--4711, 2023

    2023

  4. [12]

    Model Interpretability through the Lens of Computational Complexity

    Barcel \'o , P., Monet, M., P \'e rez, J., and Subercaseaux, B. Model Interpretability through the Lens of Computational Complexity . Proc. 33rd Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp.\ 15487--15498, 2020

    2020

  5. [13]

    Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations

    Barcel \'o , P., Kozachinskiy, A., Orth, M., Subercaseaux, B., and Verschae, J. Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations . 2025. Technical Report. https://arXiv:2501.06078

    2025

  6. [14]

    and Tinelli, C

    Barrett, C. and Tinelli, C. Satisfiability Modulo Theories . Handbook of model checking, pp.\ 305--343, 2018

    2018

  7. [15]

    and Katz, G

    Bassan, S. and Katz, G. Towards Formal XAI : Formally Approximate Minimal Explanations of Neural Networks . In Proc. Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp.\ 187--207, 2023

    2023

  8. [16]

    Formally Explaining Neural Networks Within Reactive Systems

    Bassan, S., Amir, G., Corsi, D., Refaeli, I., and Katz, G. Formally Explaining Neural Networks Within Reactive Systems . In Proc. 23rd Int. Conf. on Formal Methods in Computer-Aided Design (FMCAD), pp.\ 1--13, 2023

    2023

  9. [17]

    Local vs

    Bassan, S., Amir, G., and Katz, G. Local vs. Global Interpretability: A Computational Complexity Perspective . In Proc. 41st Int. Conf. on Machine Learning (ICML), 2024

    2024

  10. [18]

    Y., Ladner, T., Althoff, M., and Katz, G

    Bassan, S., Elboher, Y. Y., Ladner, T., Althoff, M., and Katz, G. Explaining, Fast and Slow: Abstraction and Refinement of Provable Explanations . In Proc. 42nd Int. Conf. on Machine Learning (ICML), 2025 a

    2025

  11. [19]

    Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons

    Bassan, S., Eliav, R., and Gur, S. Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons . In Proc. 13th Int. Conf. on Learning Representations (ICLR), 2025 b

    2025

  12. [20]

    Self-Explaining Neural Networks for Business Process Monitoring

    Bassan, S., Gur, S., Zeltyn, S., Mavrogiorgos, K., Eliav, R., and Kyriazis, D. Self-Explaining Neural Networks for Business Process Monitoring . 2025 c . Technical Report. https://arXiv:2503.18067

    2025 arXiv

  13. [21]

    Interpretable Random Forests via Rule Extraction

    B \'e nard, C., Biau, G., Da Veiga, S., and Scornet, E. Interpretable Random Forests via Rule Extraction . In Proc. 24th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pp.\ 937--945, 2021

    2021

  14. [22]

    On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts

    Berman, P., Karpinski, M., Larmore, L., Plandowski, W., and Rytter, W. On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts . Journal of Computer and System Sciences, 65 0 (2): 0 332--350, 2002

    2002

  15. [23]

    and Luxburg, U

    Bhattacharjee, R. and Luxburg, U. Auditing Local Explanations is Hard . In Proc. 37th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp.\ 18593--18632, 2024

    2024

  16. [24]

    Provably Efficient, Succinct, and Precise Explanations

    Blanc, G., Lange, J., and Tan, L.-Y. Provably Efficient, Succinct, and Precise Explanations . In Proc. 35th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp.\ 6129--6141, 2021

    2021

  17. [25]

    A Query-Optimal Algorithm for Finding Counterfactuals

    Blanc, G., Koch, C., Lange, J., and Tan, L.-Y. A Query-Optimal Algorithm for Finding Counterfactuals . In Proc. 39th Int. Conf. on Machine Learning (ICML), pp.\ 2075--2090, 2022

    2022

  18. [26]

    and Koriche, F

    Bounia, L. and Koriche, F. Approximating Probabilistic Explanations via Supermodular Minimization . In Proc. 39th Int. Conf. on Uncertainty in Artificial Intelligence (UAI), pp.\ 216--225, 2023

    2023

  19. [27]

    On the Complexity of Global Necessary Reasons to Explain Classification

    Calautti, M., Malizia, E., and Molinaro, C. On the Complexity of Global Necessary Reasons to Explain Classification . 2025. Technical Report. https://arXiv:2501.06766

    2025 arXiv

  20. [28]

    What Made You Do This? Understanding Black-Box Decisions with Sufficient Input Subsets

    Carter, B., Mueller, J., Jain, S., and Gifford, D. What Made You Do This? Understanding Black-Box Decisions with Sufficient Input Subsets . In 22nd Int. Conf. on Artificial Intelligence and Statistics (AISTATS), pp.\ 567--576, 2019

    2019

  21. [29]

    Efficient Maximum Clique Computation Over Large Sparse Graphs

    Chang, L. Efficient Maximum Clique Computation Over Large Sparse Graphs . In Proc. 25th ACM Int. Conf. on Knowledge Discovery & Data Mining (SIGKDD), pp.\ 529--538, 2019

    2019

  22. [30]

    Robustness Verification of Tree-Based Models

    Chen, H., Zhang, H., Si, S., Li, Y., Boning, D., and Hsieh, C.-J. Robustness Verification of Tree-Based Models . In Proc. 32nd Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), 2019

    2019

  23. [31]

    Causal Explanations for Image Classifiers

    Chockler, H., Kelly, D., Kroening, D., and Sun, Y. Causal Explanations for Image Classifiers . 2024. Technical Report. https://arXiv:2411.08875

    2024 arXiv

  24. [32]

    Cooper, M. C. and Marques-Silva, J. Tractability of Explaining Classifier Decisions . Artificial Intelligence, 2023

    2023

  25. [33]

    Parameterized Algorithms , volume 5

    Cygan, M., Fomin, F., Kowalik, ., Lokshtanov, D., Marx, D., Pilipczuk, M., Pilipczuk, M., and Saurabh, S. Parameterized Algorithms , volume 5. Springer, 2015

    2015

  26. [34]

    and Hirth, A

    Darwiche, A. and Hirth, A. On the Reasons Behind Decisions . In Proc. 24th European Conf. on Artifical Intelligence (ECAI), pp.\ 712--720, 2020

    2020

  27. [35]

    and Ji, C

    Darwiche, A. and Ji, C. On the Computation of Necessary and Sufficient Explanations . In Proc. 36th AAAI Conf. on Artificial Intelligence, pp.\ 5582--5591, 2022

    2022

  28. [36]

    and Marquis, P

    Darwiche, A. and Marquis, P. A Knowledge Compilation Map . Journal of Artificial Intelligence Research (JAIR), 17: 0 229--264, 2002

    2002

  29. [37]

    Parameterized Complexity Results for the Kemeny Rule in Judgment Aggregation

    de Haan, R. Parameterized Complexity Results for the Kemeny Rule in Judgment Aggregation . In Proc. 22nd European Conf. on Artificial Intelligence (ECAI), pp.\ 1502--1510, 2016

    2016

  30. [38]

    Parameterized Complexity in the Polynomial Hierarchy

    de Haan, R. Parameterized Complexity in the Polynomial Hierarchy. Springer, 2019

    2019

  31. [39]

    and Szeider, S

    de Haan, R. and Szeider, S. Parameterized Complexity Classes Beyond Para-NP . Journal of Computer and System Sciences, 87: 0 16--57, 2017

    2017

  32. [40]

    Explanations Based on the Missing: Towards Contrastive Explanations with Pertinent Negatives

    Dhurandhar, A., Chen, P.-Y., Luss, R., Tu, C.-C., Ting, P., Shanmugam, K., and Das, P. Explanations Based on the Missing: Towards Contrastive Explanations with Pertinent Negatives . In Proc. 31st Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), 2018

    2018

  33. [41]

    Improved Inapproximability Factors for Some p , 2009

    Dick, K., Hall, S., and Umans, C. Improved Inapproximability Factors for Some p , 2009. Technical Report

    2009

  34. [42]

    A Survey on Ensemble Learning

    Dong, X., Yu, Z., Cao, W., Shi, Y., and Ma, Q. A Survey on Ensemble Learning . Frontiers of Computer Science, 14: 0 241--258, 2020

    2020

  35. [43]

    and Fellows, M

    Downey, R. and Fellows, M. R. Parameterized Complexity . Springer Science & Business Media, 2012

    2012

  36. [44]

    and Grohe, M

    Flum, J. and Grohe, M. Describing Parameterized Complexity Classes . Information and Computation, 187 0 (2): 0 291--319, 2003

    2003

  37. [45]

    and Grohe, M

    Flum, J. and Grohe, M. The Parameterized Complexity of Counting Problems . SIAM Journal on Computing, 33 0 (4): 0 892--922, 2004

    2004

  38. [46]

    and Rubin, S

    Gorji, N. and Rubin, S. Sufficient Reasons for Classifier Decisions in the Presence of Domain Constraints . In Proc. AAAI Conference on Artificial Intelligence, pp.\ 5660--5667, 2022

    2022

  39. [47]

    Counterfactual Explanations and how to find them: Literature Review and Benchmarking

    Guidotti, R. Counterfactual Explanations and how to find them: Literature Review and Benchmarking . Data Mining and Knowledge Discovery, pp.\ 1--55, 2022

    2022

  40. [48]

    A Survey of Methods for Explaining Black Box Models

    Guidotti, R., Monreale, A., Ruggieri, S., Turini, F., Giannotti, F., and Pedreschi, D. A Survey of Methods for Explaining Black Box Models . ACM computing surveys (CSUR), 51 0 (5): 0 1--42, 2018

    2018

  41. [49]

    and Hayashi, K

    Hara, S. and Hayashi, K. Making Tree Ensembles Interpretable: A Bayesian Model Selection Approach . In Proc. 21st Int. Conf. on artificial intelligence and statistics (AISTATS), pp.\ 77--85, 2018

    2018

  42. [50]

    and Marques-Silva, J

    Huang, X. and Marques-Silva, J. Updates on the Complexity of SHAP Scores . In Proc. of the 33rd Int. Joint Conf. on Artificial Intelligence (IJCAI), pp.\ 403--412, 2024

    2024

  43. [51]

    On Efficiently Explaining Graph-Based Classifiers

    Huang, X., Izza, Y., Ignatiev, A., and Marques-Silva, J. On Efficiently Explaining Graph-Based Classifiers . In Proc. 18th Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), 2021

    2021

  44. [52]

    Feature Necessity & Relevancy in ML Classifier Explanations

    Huang, X., Cooper, M., Morgado, A., Planes, J., and Marques-Silva, J. Feature Necessity & Relevancy in ML Classifier Explanations . In Proc. 29th Int. Conf. on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), pp.\ 167--186, 2023

    2023

  45. [53]

    Abduction-Based Explanations for Machine Learning Models

    Ignatiev, A., Narodytska, N., and Marques-Silva, J. Abduction-Based Explanations for Machine Learning Models . In Proc. 33rd AAAI Conf. on Artificial Intelligence, number 01, pp.\ 1511--1519, 2019 a

    2019

  46. [54]

    On Relating Explanations and Adversarial Examples

    Ignatiev, A., Narodytska, N., and Marques-Silva, J. On Relating Explanations and Adversarial Examples . In Proc. 32nd Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), 2019 b

    2019

  47. [55]

    On Validating, Repairing and Refining Heuristic ML Explanations

    Ignatiev, A., Narodytska, N., and Marques-Silva, J. On Validating, Repairing and Refining Heuristic ML Explanations . 2019 c . Technical Report. https://arXiv:1907.02509

    2019 arXiv

  48. [56]

    Towards Formal Fairness in Machine Learning

    Ignatiev, A., Cooper, M., Siala, M., Hebrard, E., and Marques-Silva, J. Towards Formal Fairness in Machine Learning . In Proc. 26th Int. Conf. on Principles and Practice of Constraint Programming (CP), pp.\ 846--867, 2020 a

    2020

  49. [57]

    From Contrastive to Abductive Explanations and Back Again

    Ignatiev, A., Narodytska, N., Asher, N., and Marques-Silva, J. From Contrastive to Abductive Explanations and Back Again . In Proc. Int. Conf. of the Italian Association for Artificial Intelligence, pp.\ 335--355, 2020 b

    2020

  50. [58]

    J., and Marques-Silva, J

    Ignatiev, A., Izza, Y., Stuckey, P. J., and Marques-Silva, J. Using MaxSAT for Efficient Explanations of Tree Ensembles . In Proc. 36th AAAI Conf. on Artificial Intelligence, pp.\ 3776--3785, 2022

    2022

  51. [59]

    and Marques-Silva, J

    Izza, Y. and Marques-Silva, J. On Explaining Random Forests with SAT . In Proc. 30th Int. Joint Conf. on Artifical Intelligence (IJCAI), 2021

    2021

  52. [60]

    Efficient Explanations with Relevant Sets

    Izza, Y., Ignatiev, A., Narodytska, N., Cooper, M., and Marques-Silva, J. Efficient Explanations with Relevant Sets . 2021. Technical Report. https://arXiv:2106.00546

    2021 arXiv

  53. [61]

    On Computing Probabilistic Abductive Explanations

    Izza, Y., Huang, X., Ignatiev, A., Narodytska, N., Cooper, M., and Marques-Silva, J. On Computing Probabilistic Abductive Explanations . Int. Journal of Approximate Reasoning, 159: 0 108939, 2023

    2023

  54. [62]

    Distance-Restricted Explanations: Theoretical Underpinnings & Efficient implementation

    Izza, Y., Huang, X., Morgado, A., Planes, J., Ignatiev, A., and Marques-Silva, J. Distance-Restricted Explanations: Theoretical Underpinnings & Efficient implementation . In Proc. 21st Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), pp.\ 475--486, 2024

    2024

  55. [63]

    Probabilistic Stability Guarantees for Feature Attributions

    Jin, H., Xue, A., You, W., Goel, S., and Wong, E. Probabilistic Stability Guarantees for Feature Attributions . 2025. Technical Report. https://arXiv:2504.13787

    2025 arXiv

  56. [64]

    L., Julian, K., and Kochenderfer, M

    Katz, G., Barrett, C., Dill, D. L., Julian, K., and Kochenderfer, M. J. Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks . In Proc. 29th Int. Conf. on Computer Aided Verification (CAV), pp.\ 97--117, 2017

    2017

  57. [65]

    F., Hothorn, T., and Sick, B

    Kook, L., G \"o tschi, A., Baumann, P. F., Hothorn, T., and Sick, B. Deep Interpretable Ensembles . 2022. Technical Report. https://arXiv:2205.12729

    2022 arXiv

  58. [66]

    On Guaranteed Optimal Robust Explanations for NLP Models

    La Malfa, E., Zbrzezny, A., Michelmore, R., Paoletti, N., and Kwiatkowska, M. On Guaranteed Optimal Robust Explanations for NLP Models . In Proc. Int. Joint Conf. on Artificial Intelligence (IJCAI), pp.\ 2658--2665, 2021

    2021

  59. [67]

    and Lee, S.-I

    Lundberg, S. and Lee, S.-I. A Unified Approach to Interpreting Model Predictions . Proc. 30th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), 2017

    2017

  60. [68]

    and Ignatiev, A

    Marques-Silva, J. and Ignatiev, A. Delivering Trustworthy AI through formal XAI . In Proc. 36th AAAI Conf. on Artificial Intelligence, pp.\ 12342--12350, 2022

    2022

  61. [69]

    Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay

    Marques-Silva, J., Gerspacher, T., Cooper, M., Ignatiev, A., and Narodytska, N. Explaining Naive Bayes and Other Linear Classifiers with Polynomial Time and Delay . Proc. 33rd Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), pp.\ 20590--20600, 2020

    2020

  62. [70]

    C., Ignatiev, A., and Narodytska, N

    Marques-Silva, J., Gerspacher, T., Cooper, M. C., Ignatiev, A., and Narodytska, N. Explanations for Monotonic Classifiers . In Proc. 38th Int. Conf. on Machine Learning (ICML), pp.\ 7469--7479, 2021

    2021

  63. [71]

    and De La Higuera, C

    Marzouk, R. and De La Higuera, C. On the Tractability of SHAP Explanations under Markovian Distributions . In Proc. 41st Int. Conf. on Machine Learning (ICML), pp.\ 34961--34986, 2024

    2024

  64. [72]

    On the Computational Tractability of the (Many) Shapley Values

    Marzouk, R., Bassan, S., Katz, G., and la Higuera, D. On the Computational Tractability of the (Many) Shapley Values . In Proc. 28th Int. Conf. on Artificial Intelligence and Statistics (AISTATS), 2025

    2025

  65. [73]

    Chaff: Engineering an efficient SAT solver

    Moskewicz, M., Madigan, C., Zhao, Y., Zhang, L., and Malik, S. Chaff: Engineering an efficient SAT solver . In Proc. 38th Annual Design Automation Conf., pp.\ 530--535, 2001

    2001

  66. [74]

    The Parameterized Complexity of Finding Concise Local Explanations

    Ordyniak, S., Paesani, G., and Szeider, S. The Parameterized Complexity of Finding Concise Local Explanations . In Proc. 32nd Int. Joint Conf. on Artificial Intelligence (IJCAI), 2023

    2023

  67. [75]

    Explaining Decisions in ML Models: A Parameterized Complexity Analysis

    Ordyniak, S., Paesani, G., Rychlicki, M., and Szeider, S. Explaining Decisions in ML Models: A Parameterized Complexity Analysis . In Proc. 21st Int. Conf. on Principles of Knowledge Representation and Reasoning (KR), pp.\ 563--573, 2024

    2024

  68. [76]

    and Vidal, T

    Parmentier, A. and Vidal, T. Optimal Counterfactual Explanations in Tree Ensembles . In Proc. 38th Int. Conf. on Machine Learning (ICML), pp.\ 8422--8431, 2021

    2021

  69. [77]

    Anchors: High-Precision Model-Agnostic Explanations

    Ribeiro, M., Singh, S., and Guestrin, C. Anchors: High-Precision Model-Agnostic Explanations . In Proc. 32nd AAAI Conf. on Artificial Ontelligence, 2018

    2018

  70. [78]

    Interpretable machine learning: Fundamental principles and 10 grand challenges

    Rudin, C., Chen, C., Chen, Z., Huang, H., Semenova, L., and Zhong, C. Interpretable machine learning: Fundamental principles and 10 grand challenges. Statistic Surveys, 16: 0 1--85, 2022

    2022

  71. [79]

    and Rokach, L

    Sagi, O. and Rokach, L. Ensemble Learning: A Survey . Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 8 0 (4): 0 e1249, 2018

    2018

  72. [80]

    and Rokach, L

    Sagi, O. and Rokach, L. Approximating XGBoost with an Interpretable Decision Tree . Information Sciences, 572: 0 522--542, 2021

    2021

  73. [81]

    and Lange, M

    S \"a lzer, M. and Lange, M. Reachability is NP-complete even for the Simplest Neural Networks . In Proc. 15th Int. Conf. on Reachability Problems (RP), pp.\ 149--164, 2021

    2021

  74. [82]

    and Umans, C

    Schaefer, M. and Umans, C. Completeness in the Polynomial Time Hierarchy: A Compendium . SIGACT news, 33 0 (3): 0 32--49, 2002

    2002

  75. [83]

    Probabilistic Explanations for Linear Models

    Subercaseaux, B., Arenas, M., and Meel, K. Probabilistic Explanations for Linear Models . In Proc. 39th AAAI Conf. on Artificial Intelligence, number 19, pp.\ 20655--20662, 2025

    2025

  76. [84]

    and Najmi, A

    Sundararajan, M. and Najmi, A. The Many Shapley Values for Model Explanation . In Proc. 37th Int. Conf. on Machine Learning (ICML), pp.\ 9269--9278, 2020

    2020

  77. [85]

    The Minimum Equivalent DNF Problem and Shortest Implicants

    Umans, C. The Minimum Equivalent DNF Problem and Shortest Implicants . Journal of Computer and System Sciences, 63 0 (4): 0 597--611, 2001

    2001

  78. [86]

    The Complexity of Enumeration and Reliability Problems

    Valiant, L. The Complexity of Enumeration and Reliability Problems . SIAM Journal on Computing, 8 0 (3): 0 410--421, 1979

    1979

  79. [87]

    On the Tractability of SHAP Explanations

    Van den Broeck, G., Lykov, A., Schleich, M., and Suciu, D. On the Tractability of SHAP Explanations . Journal of Artificial Intelligence Research (JAIR), 74: 0 851--886, 2022

    2022

  80. [88]

    Efficient Algorithms for Clique Problems

    Vassilevska, V. Efficient Algorithms for Clique Problems . Information Processing Letters, 109 0 (4): 0 254--257, 2009

    2009

  81. [89]

    The Computational Complexity of Understanding Binary Classifier Decisions

    W \"a ldchen, S., Macdonald, J., Hauch, S., and Kutyniok, G. The Computational Complexity of Understanding Binary Classifier Decisions . Journal of Artificial Intelligence Research (JAIR), 70: 0 351--387, 2021

    2021

  82. [90]

    Probabilistic Sufficient Explanations

    Wang, E., Khosravi, P., and Van den Broeck, G. Probabilistic Sufficient Explanations . In Proc. 30th Int. Joint Conf. on Artificial Intelligence (IJCAI), 2021 a

    2021

  83. [91]

    Wang, S., Zhang, H., Xu, K., Lin, X., Jana, S., Hsieh, C.-J., and Kolter, J. Z. Beta-Crown: Efficient Bound Propagation with Per-Neuron Split Constraints for Neural Network Robustness Verification . In Proc. 35th Conf. on Advances in Neural Information Processing Systems (Neur...

    2021

  84. [92]

    Marabou 2.0: A Versatile Formal Analyzer of Neural Networks

    Wu, H., Isac, O., Zelji \'c , A., Tagomori, T., Daggitt, M., Kokke, W., Refaeli, I., Amir, G., Julian, K., Bassan, S., et al. Marabou 2.0: A Versatile Formal Analyzer of Neural Networks . In Proc. 36th Int. Conf. on Computer Aided Verification (CAV), pp.\ 249--264, 2024 a

    2024

  85. [93]

    Verix: Towards Verified Explainability of Deep Neural Networks

    Wu, M., Wu, H., and Barrett, C. Verix: Towards Verified Explainability of Deep Neural Networks . In Proc. 36th Int. Conf. on Advances in Neural Information Processing Systems (NeurIPS), 2024 b

    2024

  86. [94]

    Stability Guarantees for Feature Attributions with Multiplicative Smoothing

    Xue, A., Alur, R., and Wong, E. Stability Guarantees for Feature Attributions with Multiplicative Smoothing . In Proc. 36th Int. Conf. on Advances in Neural Information Processing Systems (Neurips), pp.\ 62388--62413, 2023

    2023

  87. [95]

    J., Narodytska, N., and Marques-Silva, J

    Yu, J., Ignatiev, A., Stuckey, P. J., Narodytska, N., and Marques-Silva, J. Eliminating the Impossible, Whatever Remains Must be True: On Extracting and Applying Background Knowledge in the Context of Formal Explanations . In Proc. 37th AAAI Conf. on Artificial Intelligence, n...

    2023

  88. [96]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.