本文研究了纯差分隐私下统计查询释放的问题。Nikolov 和 Ullman 曾提出一个猜想：对于大小为 T 的域上的 k 个统计查询，是否存在一种纯差分隐私机制，其最坏坐标误差能够达到已知下界所暗示的平方根速率。本文证明了该猜想的上界成立。具体来说，对于任意数据库大小 n 和隐私参数 ε>0，存在一个 ε-差分隐私机制，其期望误差为 O(min{1, sqrt(log(2T)log(2k)/(εn))})。这一结果在高维标准条件下匹配了下界依赖关系；通过移位对数和外层最小值，该上界在无需额外参数假设的情况下仍然有效。构造方法从一个仅基于选择的私有乘法权重记录（transcript）出发，然后用距离惩罚似然包络替换其概率质量函数。为了证明该修改保持了准确性，论文使用似然层面的 Maurey 论证，通过一小族辅助 PMW 律来界定每个汉明球的最大值。Renyi 矩界控制了邻近的球，直接混合界控制了远处的球，并且在隐私尺度处对半径进行分组，避免了误差中额外的 1/ε 因子。该机制是信息论意义上的。此外，论文还附带了一个 Lean 4 形式化验证，机器检验了有限构造、确定性解码后的纯隐私性以及显示的全范围上界。这项工作是差分隐私理论的重要进展，为统计查询释放的最优误差提供了理论支持。

该论文旨在解决机器学习模型输出结果的可公开验证性问题。作者在Goldwasser等人提出的交互式学习证明框架基础上，首次研究了非交互式学习证明，并定义了一种新概念：公开可验证的统计有效性证书（Publicly-Verifiable Certificates of Statistical Validity, pvCSVs）。该证书允许学习算法发布一个假设h及其对应的证书π，任何持有特定分布的用户都能有效验证该假设在该分布下是否有效。论文重点在自适应统计查询（Adaptive Statistical Query, SQ）算法场景下构造pvCSVs。对于进行了k次自适应查询的SQ算法，作者构建的pvCSVs的样本复杂度仅为O(log k)，而最优学习算法的样本复杂度为~O(√k)，展现了显著优势。此外，论文更广泛地研究了SQ模型中的学习证明系统，展示了该模型的优势与局限性。该工作为机器学习模型的可验证性、鲁棒性和公平性认证提供了新思路，尤其适用于需要公开验证模型性能的场景，如联邦学习、可信AI审计等。