本文研究了差分隐私（Differential Privacy, DP）下的持续计数问题（Continual Counting）。问题设定是：给定一个长度为 n 的二进制流，每个 1 代表一个个体的贡献，目标是在保护每个个体隐私的前提下，发布所有当前的累计计数。标准的算法是二叉树机制（Binary Tree Mechanism），该机制的高斯噪声变体在近似差分隐私（Approximate DP）下实现了期望的 ℓ∞ 误差为 O(log^{3/2} n)。长期以来，一个核心开放问题是：这个对数据流长度 n 的依赖关系是否是必要的？本文通过证明每个差分隐私持续计数机制都必须有期望的 ℓ∞ 误差 Ω(log^{3/2} n) 的下界，解决了这一依赖关系。这一结果表明，在近似差分隐私设定下，二叉树机制是渐近最优的。作为推论，本文还得到了线性查询的遗传差异（Hereditary Discrepancy）与私有 ℓ∞ 误差之间的最大可能分离，表明已知的基于遗传差异的通用上界对查询数量具有最优依赖关系。论文的核心方法是基于隐私损失的下界分析，利用了隐私测度的组合性质和反演技巧。主要贡献是：1）首次证明了持续计数问题在近似差分隐私下的下界，匹配二叉树机制的上界；2）揭示了遗传差异与私有误差之间关系的紧界。本文适合对差分隐私理论、数据流算法和隐私下界感兴趣的研究人员阅读。

本文研究PSPACE语言的高效交互式证明系统。经典结论IP=PSPACE表明任何PSPACE语言都存在交互式证明，但验证者高效时，证明者可能需要指数时间。后续工作致力于构造“加倍高效”的证明系统，即证明者时间为T(n)的多项式，验证者时间为输入长度n的多项式。此前最好结果由Berger等人（FOCS 2025）实现，将T(n)的上界拓展至n^{O(√(log n / log log n))}。本文将该上界进一步大幅提升至n^{O(log n)}，即任何T(n)=n^{O(log n)}时间内可判定的PSPACE语言均存在加倍高效的证明系统。方法上，不同于先前通过批量交互证明间接构造的复杂方案，本文直接构造了验证协议，不仅简化了证明过程，也为未来改进提供了更清晰的路径。实验上，本文是理论证明，无需实际实验。主要贡献：1）扩展了加倍高效证明系统的适用范围；2）提出了更简洁的直接构造方法；3）推动了复杂度理论中交互式证明的研究。适合理论计算机科学、密码学、复杂度理论研究者阅读。

本文研究了机器学习中的“遗忘”（unlearning）问题，即如何从已训练好的模型中移除某个用户数据的影响，以满足如“被遗忘权”等法律和用户需求。针对光滑强凸损失函数下的随机优化场景，前期工作已经提出了一些遗忘算法及其误差界，但遗忘的统计代价——即与从头再训练相比，遗忘算法在泛化误差上的额外成本——尚未明确。本文几乎完全解决了这一问题：作者证明了近似ε-遗忘的额外种群风险（excess population risk）的上界和下界，并且这些界除了一个条件数因子外是紧的。对于单位球上的均值估计，上下界完全匹配。最优遗忘率等于通常的统计误差加上一个遗忘惩罚项，该惩罚项在从头再训练率和随ε/d增长而指数级减小的项之间插值，其中d是模型维度。特别地，当ε远大于d时，所提出的ε-遗忘算法相比从头再训练和差分隐私基线，在精度上呈指数级提升；而当ε小于等于d时，从头再训练是最优的。该工作为理解遗忘的基本统计成本提供了理论基础。

本文研究在诚实但好奇的服务器场景下，通过本地差分隐私（LDP）对 n 个用户持有的数值进行私有求和估计。传统上，本地差分隐私要求每个用户独立添加噪声，导致估计精度远低于集中式差分隐私（CDP）——后者在汇总数据后统一添加噪声。本文证明这一精度差距并非本质性的：通过精心设计用户间本地噪声的相关性，可以构造满足 ε-差分隐私的机制，使得求和估计的均方误差（MSE）与集中式设置中可达到的最优值任意接近。具体地，作者提出一种基于相关噪声的 LDP 机制，其估计成本（MSE）与 CDP 最优成本仅相差任意小的常数倍，从而在理论上确立了 LDP 可以无损达到 CDP 的效用。该结果挑战了 LDP 必然导致高噪声损失的普遍认知，为设计高效本地隐私保护聚合协议提供了新的理论框架。论文属于理论性研究，适合对差分隐私、统计推断和隐私计算理论感兴趣的学者。