# From Pseudorandomness to Multi-Group Fairness and Back

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 47 references that are in the map.
- First posted on arXiv 21 Jan 2023.

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

- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Multiaccuracy: Black-Box Post-Processing for Fairness in Classification](https://mlsanity.com/paper/1805.12317/) (2018)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Moment Multicalibration for Uncertainty Estimation](https://mlsanity.com/paper/2008.08037/) (2020)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [Online Multivalid Learning: Means, Moments, and Prediction Intervals](https://mlsanity.com/paper/2101.01739/) (2021)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)

## Built on by (most cited first, 14 of 14)

- [When is Multicalibration Post-Processing Necessary?](https://mlsanity.com/paper/2406.06487/) (2024)
- [On Computationally Efficient Multi-Class Calibration](https://mlsanity.com/paper/2402.07821/) (2024)
- [Omnipredictors for Regression and the Approximate Rank of Convex Functions](https://mlsanity.com/paper/2401.14645/) (2024)
- [How Global Calibration Strengthens Multiaccuracy](https://mlsanity.com/paper/2504.15206/) (2025)
- [When does a predictor know its own loss?](https://mlsanity.com/paper/2502.20375/) (2025)
- [Active Fourier Auditor for Estimating Distributional Properties of ML Models](https://mlsanity.com/paper/2410.08111/) (2024)
- [Generalized and Unified Equivalences between Hardness and Pseudoentropy](https://mlsanity.com/paper/2507.05972/) (2025)
- [Improved Bounds for Swap Multicalibration and Swap Omniprediction](https://mlsanity.com/paper/2505.20885/) (2025)
- [Calibration through the Lens of Indistinguishability](https://mlsanity.com/paper/2509.02279/) (2025)
- [Supersimulators](https://mlsanity.com/paper/2509.17994/) (2025)
- [An Efficient Black-Box Reduction from Online Learning to Multicalibration, and a New Route to Phi-Regret Minimization](https://mlsanity.com/paper/2604.19592/) (2026)
- [Rules, Cases, and Reasoning: Positivist Legal Theory as a Framework for Pluralistic AI Alignment](https://mlsanity.com/paper/2410.17271/) (2024)
- [Sample-efficient Multiclass Calibration under ℓp Error](https://mlsanity.com/paper/2509.23000/) (2025)
- [Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening](https://mlsanity.com/paper/2608.05327/) (2026)

## Abstract (arXiv)

We identify and explore connections between the recent literature on multi-group fairness for prediction algorithms and the pseudorandomness notions of leakage-resilience and graph regularity. We frame our investigation using new variants of multicalibration based on statistical distance and closely related to the concept of outcome indistinguishability. Adopting this perspective leads us not only to new, more efficient algorithms for multicalibration, but also to our graph theoretic results and a proof of a novel hardcore lemma for real-valued functions.