本文研究量子计算背景下伪随机原语之间的结构性关系，重点考察伪随机状态生成器（PRSG）、伪随机函数型状态生成器（PRFSG）与伪随机酉（PRU）是否可以相互推出。核心问题是：量子态的伪随机性是否足以构造量子酉的伪随机性？作者给出了一个完整的酉 oracle 分离结果：即使采用最强的态伪随机概念——自适应安全、量子可访问的 PRFSG——也不能推出最弱的酉伪随机概念——非自适应安全、仅前向的 PRU。该分离还允许 PRFSG 的实现是非酉的，并可使用任意数量的辅助量子比特，因此结论具有很强的鲁棒性。技术路线上，作者将候选 PRU 构造视为一个从底层 oracle 状态到所实现酉的映射，并研究该映射的导数。关键观察是这些导数天然具有低秩结构，而真正随机的酉对应的高秩行为无法被此类低秩映射模拟，于是可利用低秩性质将候选构造与真随机酉区分开。论文的主要贡献在于揭示了量子态伪随机与量子酉伪随机之间存在根本区别，并提出了“微分视角”这一分析工具，可能用于研究量子态与酉的其他结构性问题。该工作属于量子密码与计算复杂性理论基础研究，适合量子密码、量子安全原语、黑盒分离与归约方向的研究者阅读。

本文从形式语言理论的角度重新审视 Emil Post 提出的“生产性集合”(productive set) 概念，并据此构造出本质上不可判定的形式文法。背景上，Post 证明存在这样一类自然数集合：它们不是递归可枚举的，甚至连半可计算都做不到——不存在任何图灵机能在有限步内枚举其全部元素，其补集可被递归枚举而集合自身不可枚举，这类集合即生产性集合；若进一步满足更强条件则称为“完全生产性”。由此可推出，任何以生产性集合作为其词集的形式语言都不可能是递归可枚举的，也就是无法被图灵机半判定，属于“本质不可判定”的语言，其地位比乔姆斯基体系中最宽的第 0 型递归可枚举语言还要“超出图灵阈值”。论文的核心方法是：把 Post 关于自然数生产性集合的经典构造（通过不断产生“新元素”，使任何候选枚举器都无法封闭其输出集合）翻译到文法规则设计中，从而显式构造出一族能够生成生产性词集的形式文法，并论证这些文法所定义的语言既不可计算也非递归可枚举。作者明确指出这是一项构造性、概念性的理论工作，而非实验性研究：其贡献在于把可计算性理论中关于不可判定性的经典边界结果系统地带入形式文法与语言层级的语境，给出“超越图灵可判定性”的文法形式刻画，并提示语言层级中存在位于递归可枚举语言之上的层次。适合可计算性理论、形式语言与自动机理论的研究者阅读，也适合关心程序分析、形式验证与静态分析工具判定边界的工程读者。

差分隐私（Differential Privacy）为数据分析提供严格的隐私保证，但在回答大量线性查询时，必须在隐私预算、响应精度和随机位数之间权衡。经典机制（如 Hardt 与 Talwar 提出的 K-范数机制）虽能在给定隐私预算 ε 下将 l∞ 误差控制在较好水平，却往往需要消耗大量随机位；而在低功耗设备或分布式场景中，高熵随机源本身是稀缺资源。本文针对这一“随机性-效用权衡”问题，提出了一个随机性有效的 K-范数机制变体：只需 O(log d) 个随机位即可回答 d 个线性查询，同时达到 O(d/ε) 的 l∞ 误差。相比 Canonne 等人的现有算法，该方案的随机位消耗显著降低；当隐私参数 ε ≤ 1/d 时，该结果在误差与随机位数上均达到渐近最优。此外，作者还给出了计算上高效的版本，以 O(log d) 倍的误差增加为代价换取更低的计算复杂度。该工作属于理论计算机科学、随机化算法与隐私计算的交叉领域，其核心贡献是证明“少量随机位也能接近最优精度”这一可达成上界，揭示了随机位数与查询精度之间的基本关系。该结果对随机性受限环境（如边缘设备上的私有数据收集）中的差分隐私系统设计有指导价值，也为后续设计低熵需求的隐私机制提供了新思路。适合研究差分隐私理论、算法机制设计及隐私增强工程化的读者阅读。

该论文从理论计算机科学的角度，系统研究了量子机器学习中“平均情况困难性”与“密码学原语”之间的深层联系。传统上，经典密码学与学习理论之间存在著名的双向蕴含关系：密码学原语可推导出学习问题的困难性，而学习问题的困难性又可反过来构造密码方案。近年来，研究者开始将这一对应关系拓展到量子领域，尤其关注量子态学习（AHL）与单向量子态生成器（OWSG）等概念的联系。然而，此前的研究大多聚焦于纯量子态，对于混合量子态情形下二者是否仍然等价，一直悬而未决。本文的主要贡献是严格证明了：混合量子态的平均情况学习困难性（AHL for mixed states）与“不可高效验证的单向量子态生成器”（IV-OWSGs）的存在性是完全等价的。这一等价关系填补了该方向的重要理论空白，并且作为直接推论，将混合态AHL与EFI（纠缠辅助的不可区分性）对联系起来——EFI对是量子密码学中一类基本且重要的资源。此外，作者利用现有结果，进一步展示了在SWAP预言机（oracle）环境下，IV-OWSGs与OWSGs之间存在可证明的分离性，从而揭示了这两类生成器在计算复杂度上的本质差异。该工作为理解量子学习困难性在密码学中的角色提供了统一框架，也为后续构建基于混合量子态的后量子密码协议奠定了理论基础。适合理论密码学、量子计算复杂性理论以及量子信息安全方向的研究者阅读。

本文研究了差分隐私（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 必然导致高噪声损失的普遍认知，为设计高效本地隐私保护聚合协议提供了新的理论框架。论文属于理论性研究，适合对差分隐私、统计推断和隐私计算理论感兴趣的学者。