双亚线性邻近交互式证明
Doubly Sub-linear Interactive Proofs of Proximity
摘要
研究提出双亚线性邻近交互式证明（dsIPP），一种用于海量输入近似断言的极速证明生成方法。证明生成仅需读取输入的一小部分（亚线性），而近似验证速度更快，仅读取更小部分。与性质检验类似，亚线性时间的诚实证明者使验证者接受性质中的每个输入，且无证明者能欺骗验证者。
我们研究双亚线性邻近交互式证明（dsIPP）：一种生成速度极快的证明，可用于证明关于海量输入的近似断言。证明生成之所以极快，是因为它只需读取输入的一小部分（亚线性）。证明的近似验证则更快（读取输入中更小的一部分）。与性质检验领域的文献类似，近似验证意味着亚线性时间的诚实证明者能让验证者接受性质中的每个输入，但没有任何证明者能欺骗验证者……
译自 Apple · ML Research · 录于 二〇二六年七月十七日