Fetching the paper…
Reading the bibliography…
Recent studies have examined the computational complexity of computing Shapley additive explanations (also known as SHAP) across various models and distributions, revealing their tractability or intractability in different settings.
An Introduction to Hidden Markov Models
L. Rabiner and B. Juang · 1986
Earlier work this paper cites.
Rational Series and their Languages
J. Berstel and C. Reutenauer · 1988
Earlier work this paper cites.
Hidden Markov Models in Speech and Language Processing
K. Knill and S. Young · 1997
Earlier work this paper cites.
On the Closest String and Substring Problems
M. Li, B. Ma, and L. Wang · 2002
Earlier work this paper cites.
Hidden Markov Models in Bioinformatics
V. De Fonzo, F. Aluffi-Pentini, and V. Parisi · 2007
Earlier work this paper cites.
Computational Complexity: a Modern Approach
S. Arora and B. Barak · 2009
Earlier work this paper cites.
Handbook of Weighted Automata
M. Droste, W. Kuich, and H. Vogler · 2009
Earlier work this paper cites.
On the Complexity of Problems on Simple Games
J. Freixas, X. Molinero, M. Olsen, and M. Serna · 2011
Earlier work this paper cites.
Parameterized Complexity
R. Downey and M. Fellows · 2012
Earlier work this paper cites.
A Spectral Algorithm for Learning Hidden Markov Models
D. Hsu, S. M. Kakade, and T. Zhang · 2012
Earlier work this paper cites.
Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks
G. Katz, C. Barrett, D. Dill, K. Julian, and M. J. Kochenderfer · 2017
Earlier work this paper cites.
A Unified Approach to Interpreting Model Predictions
S. Lundberg and S.-I. Lee · 2017
Earlier work this paper cites.
Satisfiability Modulo Theories
C. Barrett and C. Tinelli · 2018
Earlier work this paper cites.
Abduction-based Explanations for Machine Learning Models
A. Ignatiev, N. Narodytska, and J. Marques-Silva · 2019
Earlier work this paper cites.
Learning Deterministic Weighted Automata with Queries and Counterexamples
G. Weiss, Y. Goldberg, and E. Yahav · 2019
Earlier work this paper cites.
Model Interpretability Through the Lens of Computational Complexity
P. Barceló, M. Monet, J. Pérez, and B. Subercaseaux · 2020
Earlier work this paper cites.
Causality-Based Explanation of Classification Outcomes
L. Bertossi, J. Li, M. Schleich, and D. S. Z. Vagena · 2020
Earlier work this paper cites.
Understanding Global Feature Contributions with Additive Importance Measures
I. Covert, S. M. Lundberg, and S.-I. Lee · 2020
Earlier work this paper cites.
On the Reasons Behind Decisions
A. Darwiche and A. Hirth · 2020
Earlier work this paper cites.
Causal Shapley Values: Exploiting Causal Knowledge to Explain Individual Predictions of Complex Models
T. Heskes, E. Sijben, I. G. Bucur, and T. Claassen · 2020
Earlier work this paper cites.
Towards Trustable Explainable AI
A. Ignatiev · 2020
Earlier work this paper cites.
Feature Relevance Quantification in Explainable AI: A Causal Problem
D. Janzing, L. Minorics, and P. Bloebaum · 2020
Cited alongside, same era.
Problems with Shapley-value-based Explanations as Feature Importance Measures
I. Kumar, S. Venkatasubramanian, C. Scheidegger, and S. Friedler · 2020
Cited alongside, same era.
From Local Explanations to Global Understanding with Explainable AI for Trees
S. Lundberg, E. Gabriel, H. Chen, A. DeGrave, J. Prutkin, B. Nair, R. Katz, J. Himmelfarb, N. Bansal, and S.-I. Lee · 2020
Cited alongside, same era.
Weighted Automata Extraction from Recurrent Neural Networks via Regression on State Spaces
T. Okudono, M. Waga, T. Sekiyama, and I. Hasuo · 2020
Cited alongside, same era.
The Many Shapley Values for Model Explanation
M. Sundararajan and A. Najmi · 2020
Cited alongside, same era.
The Shapley Taylor Interaction Index
M. Sundararajan, K. Dhamdhere, and A. Agarwal · 2020
Formally Explaining Neural Networks within Reactive Systems
S. Bassan, G. Amir, D. Corsi, I. Refaeli, and G. Katz · 2023
Later among the works it cites.
The Shapley Value in Database Management
L. Bertossi, B. Kimelfeld, E. Livshits, and M. Monet · 2023
Later among the works it cites.
Tractability of Explaining Classifier Decisions
M. C. Cooper and J. Marques-Silva · 2023
Later among the works it cites.
The Inadequacy of Shapley Values for Explainability
X. Huang and J. Marques-Silva · 2023
Later among the works it cites.
Logic-based Explainability in Machine Learning
J. Marques-Silva · 2023
Later among the works it cites.
The Parameterized Complexity of Finding Concise Local Explanations
S. Ordyniak, G. Paesani, and S. Szeider · 2023
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Explaining Individual Predictions when Features are Dependent: More Accurate Approximations to Shapley Values
K. Aas, M. Jullum, and A. Løland · 2021
Cited alongside, same era.
Provably Efficient, Succinct, and Precise Explanations
G. Blanc, J. Lange, and L.-Y. Tan · 2021
Cited alongside, same era.
Approximating the Shapley Value Using Stratified Empirical Bernstein Sampling
M. A. Burgess and A. C. Chapman · 2021
Cited alongside, same era.
Shapley Values for Feature Selection: The Good, the Bad, and the Axioms
D. Fryer, I. Strümke, and H. Nguyen · 2021
Cited alongside, same era.
Efficient Computation and Analysis of Distributional Shapley Values
Y. Kwon, M. Rivas, and J. Zou · 2021
Cited alongside, same era.
Extracting Weighted Automata for Approximate Minimization in Language Modelling
C. Lacroce, P. Panangaden, and G. Rabusseau · 2021
Cited alongside, same era.
Later among the works it cites.
Manifold Restricted Interventional Shapley Values
M. Taufiq, P. Blöbaum, and L. Minorics · 2023
Later among the works it cites.
Banzhaf Values for Facts in Query Answering
O. Abramovich, D. Deutch, N. Frost, A. Kara, and D. Olteanu · 2024
Later among the works it cites.
The Computational Complexity of Circuit Discovery for Inner Interpretability
F. Adolfi, M. Vilas, and T. Wareham · 2024
Later among the works it cites.
Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation
G. Amir, S. Bassan, and G. Katz · 2024
Later among the works it cites.
Local vs. Global Interpretability: A Computational Complexity Perspective
S. Bassan, G. Amir, and G. Katz · 2024
Later among the works it cites.
Distillation of Weighted Automata from Recurrent Neural Networks using a Spectral Approach
R. Eyraud and S. Ayache · 2024
Later among the works it cites.
SHAP-IQ: Unified Approximation of Any-Order Shapley Interactions
F. Fumagalli, M. Muschalik, P. Kolpaczki, E. Hüllermeier, and B. Hammer · 2024
Later among the works it cites.
Distance-Restricted Explanations: Theoretical Underpinnings & Efficient Implementation
Y. Izza, X. Huang, A. Morgado, J. Planes, A. Ignatiev, and J. Marques-Silva · 2024
Later among the works it cites.
From Shapley Value to Model Counting and Back
A. Kara, D. Olteanu, and D. Suciu · 2024
Later among the works it cites.
Expected Shapley-like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases
P. Karmakar, M. Monet, P. Senellart, and S. Bressan · 2024
Later among the works it cites.
Explainability is NOT a Game
J. Marques-Silva and X. Huang · 2024
Later among the works it cites.
On the Tractability of SHAP Explanations under Markovian Distributions
R. Marzouk and C. De La Higuera · 2024
Later among the works it cites.
Marabou 2.0: A Versatile Formal Analyzer of Neural Networks
H. Wu, O. Isac, A. Zeljić, T. Tagomori, M. Daggitt, W. Kokke, I. Refaeli, G. Amir, K. Julian, S. Bassan, et al · 2024
Later among the works it cites.
Explain Yourself, Briefly! Self-Explaining Neural Networks with Concise Sufficient Reasons
S. Bassan, R. Eliav, and S. Gur · 2025
Closest in time.
On the Complexity of Global Necessary Reasons to Explain Classification
M. Calautti, E. Malizia, and C. Molinaro · 2025
Closest in time.