Quantum Advantage has Few Complexity Implications
说明量子优势的复杂性含义有限
简介本文探讨量子性证明（proofs of quantumness）与（量子验证者）不可知态制备的复杂性含义。作者给出经典预言机证据，表明二者可以与非确定性计算的简单性（P = NP）并存，且（量子验证者）不可知态制备可与 BQP = QCMA 并存。文中还据此推出关于相关密码学构造的若干相对化结论。
本页没有符合条件的条目（筛选只在本页内进行）。
★★★★☆ 值得关注
Information Loss Is All You Need: TC⁰ Pseudorandomness from Worst-Case Lattices
说明信息丢失即所需：基于最坏情形格的 TC⁰ 伪随机性
简介本文提出“代数舍入学习”（LAR）方法，对秘密相关的线性测量分块做确定性整数舍入，并将结果编码到格商中。在多项式界的模数和维度下，作者证明该确定性标签在不依赖秘密的均匀公开矩阵上，对多项式数量的经典随机样本与独立均匀标签计算不可区分。安全性依赖于一般格上近似因子为 Õ(q) 的 GapSVP 与 SIVP 的量子最坏情形困难性。由此得到首个可在 TC⁰ 中联合计算密钥与输入的后量子弱伪随机函数，并证明了从无噪均匀随机样本学习多项式规模双隐层 ReLU 网络的困难性。
看点提出确定性取整的学习型舍入（LAR），以最坏情形格问题为基础构造TC0伪随机函数，并给出两层ReLU网络硬度结果，摘要报告其证明与参数设定。
★★★★☆ 值得关注
The Power of Interaction in Locally Edge-Private Subgraph Counting
说明交互式本地边隐私下的子图计数：一轮交互即可显著提高准确性
简介论文研究在交互式本地边差分隐私（LEDP）下对任意无向图进行（非诱导）子图计数。作者提出两轮算法线性噪声消除（LNC），对所有图均给出 O(n^{k-3/2}/ε^ℓ) 的误差，并证明交互可在最坏情况下多项式级地改善准确性。另提出预测与修正（PC）框架，在最大度有界的图上给出进一步的误差界，并证明与之匹配的下界。
看点提出线性噪声消除方法，两轮交互使三角形加性误差改进√n倍，并给出匹配下界，数学上的紧界。