详细内容或原文请订阅后点击阅览
一般分布属性的交互式证明
假设 Alice 从未知分布中收集了少量样本，并且想了解该分布。鲍勃是一位不受信任的数据分析师，他声称已经对分布进行了复杂的数据分析，并对其属性做出了断言。 Alice 何时以及如何有效地验证 Bob 的声明（使用比自己运行分析所需的资源更少的资源）？我们为可以由有界深度电路决定的一般分布属性构建了交互式证明系统。取 N 为分布的上限...
来源:Apple机器学习研究假设 Alice 从未知分布中收集了少量样本，并且想了解该分布。鲍勃是一位不受信任的数据分析师，他声称已经对分布进行了复杂的数据分析，并对其属性做出了断言。 Alice 何时以及如何有效地验证 Bob 的声明（使用比自己运行分析所需的资源更少的资源）？我们为可以由有界深度电路决定的一般分布属性构建了交互式证明系统。假设N是分布支持大小的上限，D是得到分布完整描述并决定属性的均匀布尔电路深度的界限，则验证者的样本复杂度、运行时间和通信复杂度都以Õ(D+N^0.99)为界。轮数为O(D·log(N))。该证明系统具有双重效率：诚实的证明者以多项式时间和准线性样本复杂度运行。我们还展示了可由有界深度图灵机（将分布的完整描述作为输入）决定的属性的类似结果。我们注意到，即使对于简单的属性，在没有证明者的情况下决定属性也需要准线性样本复杂性和运行时间。之前的工作 [Herman 和 Rothblum，FOCS 2023] 演示了次线性交互式证明系统，但仅适用于更受限制的标签不变分布属性类别。