# Hardness of Deceptive Certificate Selection

arXiv: https://arxiv.org/abs/2306.04505 · HTML: https://mlsanity.com/paper/2306.04505/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 19 of its 28 references that are in the map.
- First posted on arXiv 7 Jun 2023.

## Builds on (most cited first, 19 of 19)

- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Fooling LIME and SHAP: Adversarial Attacks on Post hoc Explanation Methods](https://mlsanity.com/paper/1911.02508/) (2019)
- [Unmasking Clever Hans Predictors and Assessing What Machines Really Learn](https://mlsanity.com/paper/1902.10178/) (2019)
- [Learning to Explain: An Information-Theoretic Perspective on Model Interpretation](https://mlsanity.com/paper/1802.07814/) (2018)
- [Invariant Rationalization](https://mlsanity.com/paper/2003.09772/) (2020)
- [What do we need to build explainable AI systems for the medical domain?](https://mlsanity.com/paper/1712.09923/) (2017)
- [Counterfactual Explanations Can Be Manipulated](https://mlsanity.com/paper/2106.02666/) (2021)
- [Rethinking Cooperative Rationalization: Introspective Extraction and Complement Control](https://mlsanity.com/paper/1910.13294/) (2019)
- [Fairwashing Explanations with Off-Manifold Detergent](https://mlsanity.com/paper/2007.09969/) (2020)
- [A Review of Feature Selection Methods Based on Mutual Information](https://mlsanity.com/paper/1509.07577/) (2015)
- [A Game Theoretic Approach to Class-wise Selective Rationalization](https://mlsanity.com/paper/1910.12853/) (2019)
- [Learning to Give Checkable Answers with Prover-Verifier Games](https://mlsanity.com/paper/2108.12099/) (2021)
- [Interpretable by Design: Learning Predictors by Composing Interpretable Queries](https://mlsanity.com/paper/2207.00938/) (2022)
- [Analyzing Classifiers: Fisher Vectors and Deep Neural Networks](https://mlsanity.com/paper/1512.00172/) (2015)
- [A Rate-Distortion Framework for Explaining Neural Network Decisions](https://mlsanity.com/paper/1905.11092/) (2019)
- [Interpretability Guarantees with Merlin-Arthur Classifiers](https://mlsanity.com/paper/2206.00759/) (2022)
- [Minimizing the Union: Tight Approximations for Small Set Bipartite Vertex Expansion](https://mlsanity.com/paper/1611.07866/) (2016)
- [Training Characteristic Functions with Reinforcement Learning: XAI-methods play Connect Four](https://mlsanity.com/paper/2202.11797/) (2022)

## Abstract (arXiv)

Recent progress towards theoretical interpretability guarantees for AI has been made with classifiers that are based on interactive proof systems. A prover selects a certificate from the datapoint and sends it to a verifier who decides the class. In the context of machine learning, such a certificate can be a feature that is informative of the class. For a setup with high soundness and completeness, the exchanged certificates must have a high mutual information with the true class of the datapoint. However, this guarantee relies on a bound on the Asymmetric Feature Correlation of the dataset, a property that so far is difficult to estimate for high-dimensional data. It was conjectured in W"aldchen et al. that it is computationally hard to exploit the AFC, which is what we prove here. We consider a malicious prover-verifier duo that aims to exploit the AFC to achieve high completeness and soundness while using uninformative certificates. We show that this task is mathsfNP-hard and cannot be approximated better than O(m1/8 - ε), where m is the number of possible certificates, for ε>0 under the Dense-vs-Random conjecture. This is some evidence that AFC should not prevent the use of interactive classification for real-world tasks, as it is computationally hard to be exploited.