双亚线性交互式接近性证明
本文研究双亚线性交互式接近性证明（dsIPPs），这是一种超快速生成和验证的证明系统，可用于证明关于海量输入的近似断言。证明者只需读取输入的一小部分（亚线性），而验证者读取的部分更少。作者为任意可由常宽度一次性无记忆分支程序（ROOBP）决定的属性构造了此类系统，还构建了针对输入汉明重量近似验证以及有界度图模型中二分性松弛的证明系统。
双亚线性交互式接近性证明（dsIPPs）是一种新颖的证明系统，旨在解决海量数据场景下的高效验证问题。传统交互式证明要求证明者读取整个输入才能生成证明，而dsIPP将这一要求降低到只需读取输入的一小部分（亚线性），验证者甚至可以读取更少的数据。这种近似验证的思想源于属性测试（property testing）领域，即验证者不需要精确判断输入是否满足属性，只需判断输入是否“接近”满足该属性。在dsIPP中，诚实的证明者可以在亚线性时间内使验证者接受所有属于该属性的输入，而任何恶意的证明者都无法使验证者接受远离该属性的输入。
该研究由魏茨曼科学研究所的Noga Amir、Oded Goldreich和Guy N. Rothblum共同完成。他们首先为任意可由常宽度一次性无记忆分支程序（ROOBP）决定的属性构造了通用的dsIPP。ROOBP是一类重要的计算模型，它允许一次读取输入比特且不保留状态，常宽度意味着使用的内存很小。这类模型覆盖了许多自然属性，如某些图性质或布尔函数。此外，他们还针对输入汉明重量（即1的个数）的近似验证设计了一个dsIPP，允许证明者在不读取整个输入的情况下证明输入中1的个数大约为某个值。针对有界度图模型，他们还构造了二分性（bipartiteness）的松弛版本的dsIPP，即证明图是否接近二分图。
这些成果的理论意义在于，它展示了即使在证明者无法完全读取输入的情况下，仍能提供可验证的证明。实际应用中，这对于大规模数据集（如基因组数据、网络流量、社交网络图等）的验证非常有用，因为读取整个数据集的成本可能过高。与传统的交互式证明相比，dsIPP显著降低了证明者的计算开销，使得原本不可行的验证任务变得可能。例如，在处理一个包含数十亿条记录的数据库时，证明者只需读取其中的一小部分即可证明整个数据库满足某个全局性质。该论文发表于2026年7月，并被顶级会议FOCS接收。未来，该工作可能推动更高效验证协议的发展，并进一步缩小理论计算机科学与实际大数据分析之间的差距。