From Pseudorandomness to Multigroup Fairness and Back

As the prevalence of machine learning expands across diverse domains, the role of algorithms in influencing decisions that significantly impact our lives becomes increasingly important. Concerns regarding the fairness of algorithmic decisions have spurred the proposal and investigation of the framework of multigroup fairness, which provides a mathematical foundation for assessing fairness across numerous overlapping subpopulations.

In this talk in the Simons Institute’s recent workshop on Multigroup Fairness and the Validity of Statistical Judgment, Huijia (Rachel) Lin (University of Washington) elucidates the close relationships among several recently proposed notions of multigroup fairness, namely, multi-accuracy, multi-calibration, and outcome indistinguishability, and concepts of pseudorandomness from complexity theory and cryptography, specifically leakage simulation in cryptography, weak regularity in complexity theory, and graph regularity in graph theory. By exploring these connections, Lin demonstrates that ideas in either area can lead to improvement in the other.