# Generalized and Unified Equivalences between Hardness and Pseudoentropy

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 41 references that are in the map.
- First posted on arXiv 8 Jul 2025.

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

- [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)
- [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)
- [Near-Optimal Algorithms for Omniprediction](https://mlsanity.com/paper/2501.17205/) (2025)
- [Complexity-Theoretic Implications of Multicalibration](https://mlsanity.com/paper/2312.17223/) (2023)
- [On Computationally Efficient Multi-Class Calibration](https://mlsanity.com/paper/2402.07821/) (2024)
- [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)
- [Omnipredicting Single-Index Models with Multi-Index Models](https://mlsanity.com/paper/2411.13083/) (2024)
- [Characterizing the Distinguishability of Product Distributions through Multicalibration](https://mlsanity.com/paper/2412.03562/) (2024)
- [Simulating Auxiliary Inputs, Revisited](https://mlsanity.com/paper/1503.00484/) (2015)
- [Generative Models of Huge Objects](https://mlsanity.com/paper/2302.12823/) (2023)

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

- [Efficient Swap Multicalibration of Elicitable Properties](https://mlsanity.com/paper/2511.04907/) (2025)
- [Supersimulators](https://mlsanity.com/paper/2509.17994/) (2025)
- [Efficient Calibration for Decision Making](https://mlsanity.com/paper/2511.13699/) (2025)
- [Simultaneous Blackwell Approachability and Applications to Multiclass Omniprediction](https://mlsanity.com/paper/2602.17577/) (2026)
- [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)

## Abstract (arXiv)

Pseudoentropy characterizations give quantitatively precise formulations of the relationship between computational hardness and computational randomness. We prove a unified pseudoentropy characterization that generalizes and strengthens previous results in both uniform and nonuniform models of computation. Our characterization applies to a general family of entropy notions, including Shannon entropy and min-entropy as special cases. Moreover, the characterizations for these different entropy notions can be witnessed simultaneously by a single universal function, which captures both computational hardness and computational randomness. A key technical insight is that weight-restricted calibration, from the recent literature on algorithmic fairness, together with standard computational indistinguishability (known as multiaccuracy in the fairness literature), suffices for proving pseudoentropy characterizations for general entropy notions. To obtain this combination of properties, we prove an enhanced version of the Leakage Simulation Lemma (Jetchev and Pietrzak, 2014), which in turn extends the Complexity Theoretic-Regularity Lemma (Trevisan, Tulsiani, and Vadhan, 2009) from boolean functions to ones over a larger alphabet. Our Enhanced Regularity/Leakage-Simulation Lemma enables us to obtain an exponential improvement in the dependence on the alphabet size compared with the pseudoentropy characterizations of Casacuberta, Dwork, and Vadhan (2024), which are based on the stronger notion of multicalibration. We also show that this exponential dependence on the alphabet size is inevitable for multicalibration and even for the weaker notion of calibrated multiaccuracy.