Data Science Group @BCAM | Chow's theorem: a spectral analysis of rankings on finite groups

Abstract​

The study of rankings generated by functions over finite groups is of particular relevance in combinatorial optimization. Many of the most widely used meta-heuristic algorithms in the literature depend exclusively on these rankings, exhibiting identical behavior for any pair of functions that induce the same ordering of elements in the search space. However, the structural properties of such rankings remain poorly understood in general. In this work, we expand this knowledge by focusing on the specific case of pseudo-Boolean functions. To that end, we extend the classical Chow's theorem from threshold function analysis and show that some fundamental results can be naturally translated to rankings. We also examine the spectral properties of two special classes of rankings and relate these properties to the functions that induce them. Finally, we propose an extension of the introduced framework to permutation-based functions. Overall, this work opens a new perspective on rankings over finite groups, aiming to leverage existing results in Fourier analysis for the study and development of optimization algorithms.