标题： 硬度与伪熵之间的广义和统一等价性 显示英文标题

标题： Generalized and Unified Equivalences between Hardness and Pseudoentropy

摘要： 伪熵特征提供了一种定量精确的证明，展示了计算难度与计算随机性之间的紧密关系。 我们证明了一个统一的伪熵特征，该特征推广并加强了对均匀和非均匀计算模型的先前结果。 我们的特征适用于一个广泛的熵概念家族，该家族包括香农熵和最小熵等常见概念作为特例。 此外，我们表明，通过一个单一的通用函数可以同时实现不同熵概念的特征，该函数同时见证计算难度和计算随机性。 我们工作的关键技术见解是，最近关于算法公平性的文献中提出的权重限制校准概念，以及标准的计算不可区分性（在公平性文献中称为多准确性），足以证明一般熵概念的伪熵特征。 这展示了权重限制校准的力量，可以增强经典的复杂性理论正则性引理（Trevisan, Tulsiani 和 Vadhan, 2009）和泄漏模拟引理（Jetchev 和 Pietrzak, 2014），使我们在字母表大小的复杂度依赖性上相比基于更强的多校准概念的 Casacuberta, Dwork 和 Vadhan (2024) 的伪熵特征实现了指数级的改进。 我们证明，对于多校准以及较弱的校准多准确性概念，字母表大小的指数依赖性是不可避免的。 显示英文摘要

摘要： Pseudoentropy characterizations provide a quantitatively precise demonstration of the close relationship between computational hardness and computational randomness. We prove a unified pseudoentropy characterization that generalizes and strengthens previous results for both uniform and non-uniform models of computation. Our characterization holds for a general family of entropy notions that encompasses the common notions of Shannon entropy and min entropy as special cases. Moreover, we show that the characterizations for different entropy notions can be simultaneously achieved by a single, universal function that simultaneously witnesses computational hardness and computational randomness. A key technical insight of our work is that the notion of weight-restricted calibration from the recent literature on algorithm fairness, along with standard computational indistinguishability (known as multiaccuracy in the fairness literature), suffices for proving pseudoentropy characterizations for general entropy notions. This demonstrates the power of weight-restricted calibration to enhance the classic Complexity-Theoretic Regularity Lemma (Trevisan, Tulsiani, and Vadhan, 2009) and Leakage Simulation Lemma (Jetchev and Pietrzak, 2014) and allows us to achieve an exponential improvement in the complexity dependency on the alphabet size compared to the pseudoentropy characterizations by Casacuberta, Dwork, and Vadhan (2024) based on the much stronger notion of multicalibration. We show that the exponential dependency on the alphabet size is inevitable for multicalibration as well as for the weaker notion of calibrated multiaccuracy.