# Complexity-Theoretic Implications of Multicalibration

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Dec 2023.

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

- [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)
- [Generalized and Unified Equivalences between Hardness and Pseudoentropy](https://mlsanity.com/paper/2507.05972/) (2025)
- [Efficient Swap Multicalibration of Elicitable Properties](https://mlsanity.com/paper/2511.04907/) (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)
- [Efficient Calibration for Decision Making](https://mlsanity.com/paper/2511.13699/) (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)
- [The Sample Complexity of Smooth Boosting and the Tightness of the Hardcore Theorem](https://mlsanity.com/paper/2409.11597/) (2024)
- [Multicalibration Yields Better Matchings](https://mlsanity.com/paper/2511.11413/) (2025)
- [Optimal Deterministic Multicalibration and Omniprediction](https://mlsanity.com/paper/2606.20557/) (2026)
- [Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria](https://mlsanity.com/paper/2609.22757/) (2026)
- [Testing Distributions Against Bounded Distinguishers](https://mlsanity.com/paper/2607.15645/) (2026)
- [Defensive Boosting for Online Probabilistic Forecasting](https://mlsanity.com/paper/2608.13554/) (2026)
- [Augmented Feature Boosting for Multicalibration](https://mlsanity.com/paper/2609.33891/) (2026)

## Abstract (arXiv)

We present connections between the recent literature on multigroup fairness for prediction algorithms and classical results in computational complexity. Multiaccurate predictors are correct in expectation on each member of an arbitrary collection of pre-specified sets. Multicalibrated predictors satisfy a stronger condition: they are calibrated on each set in the collection. Multiaccuracy is equivalent to a regularity notion for functions defined by Trevisan, Tulsiani, and Vadhan (2009). They showed that, given a class F of (possibly simple) functions, an arbitrarily complex function g can be approximated by a low-complexity function h that makes a small number of oracle calls to members of F, where the notion of approximation requires that h cannot be distinguished from g by members of F. This complexity-theoretic Regularity Lemma is known to have implications in different areas, including in complexity theory, additive number theory, information theory, graph theory, and cryptography. Starting from the stronger notion of multicalibration, we obtain stronger and more general versions of a number of applications of the Regularity Lemma, including the Hardcore Lemma, the Dense Model Theorem, and the equivalence of conditional pseudo-min-entropy and unpredictability. For example, we show that every boolean function (regardless of its hardness) has a small collection of disjoint hardcore sets, where the sizes of those hardcore sets are related to how balanced the function is on corresponding pieces of an efficient partition of the domain.