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

Marcelo Arenas, Pablo Barceló, Leopoldo E. Bertossi, Mikaël Monet

BibTeX
@article{arenas2023complexity,
  author = {Marcelo Arenas and Pablo Barceló and Leopoldo E. Bertossi and Mikaël Monet},
  title = {{On the Complexity of SHAP-Score-Based Explanations: Tractability via Knowledge Compilation and Non-Approximability Results}},
  journal = {J. Mach. Learn. Res.},
  year = {2023},
  url = {https://openreview.net/forum?id=HeIASYtsNF7},
}
Figure