# Supersimulators

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 11 of its 37 references that are in the map.
- First posted on arXiv 22 Sep 2025.

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

- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Outcome Indistinguishability](https://mlsanity.com/paper/2011.13426/) (2020)
- [Omnipredictors](https://mlsanity.com/paper/2109.05389/) (2021)
- [Loss Minimization through the Lens of Outcome Indistinguishability](https://mlsanity.com/paper/2210.08649/) (2022)
- [Low-Degree Multicalibration](https://mlsanity.com/paper/2203.01255/) (2022)
- [Loss Minimization Yields Multicalibration for Large Neural Networks](https://mlsanity.com/paper/2304.09424/) (2023)
- [Complexity-Theoretic Implications of Multicalibration](https://mlsanity.com/paper/2312.17223/) (2023)
- [From Pseudorandomness to Multi-Group Fairness and Back](https://mlsanity.com/paper/2301.08837/) (2023)
- [How Global Calibration Strengthens Multiaccuracy](https://mlsanity.com/paper/2504.15206/) (2025)
- [Generalized and Unified Equivalences between Hardness and Pseudoentropy](https://mlsanity.com/paper/2507.05972/) (2025)
- [Characterizing the Distinguishability of Product Distributions through Multicalibration](https://mlsanity.com/paper/2412.03562/) (2024)

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

- [Efficient Swap Multicalibration of Elicitable Properties](https://mlsanity.com/paper/2511.04907/) (2025)
- [The Sample Complexity of Multicalibration](https://mlsanity.com/paper/2604.21923/) (2026)
- [Optimal Deterministic Multicalibration and Omniprediction](https://mlsanity.com/paper/2606.20557/) (2026)
- [Sample Complexity of Multicalibration for Multilevel Properties](https://mlsanity.com/paper/2608.04288/) (2026)

## Abstract (arXiv)

We prove that every randomized Boolean function admits a supersimulator: a randomized polynomial-size circuit whose output on random inputs cannot be efficiently distinguished from reality with constant advantage, even by polynomially larger distinguishers. Our result builds on the landmark complexity-theoretic regularity lemma of Trevisan, Tulsiani and Vadhan (2009), which, in contrast, provides a simulator that fools smaller distinguishers. We circumvent lower bounds for the simulator size by letting the distinguisher size bound vary with the target function, while remaining below an absolute upper bound independent of the target function. This dependence on the target function arises naturally from our use of an iteration technique originating in the graph regularity literature. The simulators provided by the regularity lemma and recent refinements thereof, known as multiaccurate and multicalibrated predictors, respectively, as per Hebert-Johnson et al. (2018), have previously been shown to have myriad applications in complexity theory, cryptography, learning theory, and beyond. We first show that a recent multicalibration-based characterization of the computational indistinguishability of product distributions actually requires only (calibrated) multiaccuracy. We then show that supersimulators yield an even tighter result in this application domain, closing a complexity gap present in prior versions of the characterization.