Abstract We use social choice theory to develop correlation coeffiffifficients between ranked preferences and an ordinal attribute such as educational attainment or income level. For example, such correlations could be used to formalise statements such as “voters’ preferences over parties are better explained by age than by income level”. In the literature, preferences that are perfectly explained by a single-dimensional agent attribute are commonly taken to be singlecrossing preferences. Thus, to quantify how well an attribute explains preferences, we can order the voters by the value of the attribute and compute how far the resulting ordered profifile is from being singlecrossing, for various commonly studied distance measures (Kendall tau distance, voter/alternative deletion, etc.). The goal of this paper is to evaluate the computational feasibility of this approach. To this end, we investigate the complexity of computing these distances, obtaining an essentially complete picture for the distances we consider