  The ability to interpret Machine Learning (ML) models is becoming
increasingly essential. However, despite significant progress in the field,
there remains a lack of rigorous characterization regarding the innate
interpretability of different models. In an attempt to bridge this gap, recent
work has demonstrated that it is possible to formally assess interpretability
by studying the computational complexity of explaining the decisions of various
models. In this setting, if explanations for a particular model can be obtained
efficiently, the model is considered interpretable (since it can be explained
``easily''). However, if generating explanations over an ML model is
computationally intractable, it is considered uninterpretable. Prior research
identified two key factors that influence the complexity of interpreting an ML
model: (i) the type of the model (e.g., neural networks, decision trees, etc.);
and (ii) the form of explanation (e.g., contrastive explanations, Shapley
values, etc.). In this work, we claim that a third, important factor must also
be considered for this analysis -- the underlying distribution over which the
explanation is obtained. Considering the underlying distribution is key in
avoiding explanations that are socially misaligned, i.e., convey information
that is biased and unhelpful to users. We demonstrate the significant influence
of the underlying distribution on the resulting overall interpretation
complexity, in two settings: (i) prediction models paired with an external
out-of-distribution (OOD) detector; and (ii) prediction models designed to
inherently generate socially aligned explanations. Our findings prove that the
expressiveness of the distribution can significantly influence the overall
complexity of interpretation, and identify essential prerequisites that a model
must possess to generate socially aligned explanations.
