详细内容或原文请订阅后点击阅览
函数的位置不变属性与分布属性：在测试中统一，在验证中分离
如果函数的属性可以用函数中每个值出现的频率来表征，而不管每个值出现的位置如何，则该属性称为位置不变（或对称）。众所周知，测试函数位置不变属性的（查询）复杂性与测试相应分布（的相应属性）的（样本）复杂性密切相关。当前工作的主要信息是，这种密切关系并没有在验证的背景下维持。当考虑到......时这两者都成立
来源:Apple机器学习研究如果函数的属性可以用函数中每个值出现的频率来表征，而不管每个值出现的位置如何，则该属性称为位置不变（或对称）。众所周知，测试函数位置不变属性的（查询）复杂性与测试相应分布（的相应属性）的（样本）复杂性密切相关。当前工作的主要信息是，这种密切关系并没有在验证的背景下维持。当考虑通过一般交互式邻近证明（即 IPP）进行验证时以及限制对双次线性 IPP（ds-IPP）的关注时，这一点都成立。或者，人们可以将这项工作视为双次线性 IPP（函数属性）研究的后续步骤，如果（1）验证者的查询复杂度在测试属性的查询复杂度中是次线性的，并且（2）诚实证明者的查询复杂度在学习属性中的函数的查询复杂度中是次线性的，则我们说 IPP 是双次线性的。具体来说，我们提出了几个自然位置不变属性的双次线性 IPP。我们的结果包括：（1）我们为从 [m] 到 [n] 的函数集提出了双次线性 IPP，其中每个值出现 m/n 次：对于每个 α ∈ (0, 0.5)，验证者的查询复杂度为 O(n^{0.5−α})，诚实证明者的查询复杂度为 e^{O(n^{0.5+α}/ε^2)}。 (2) 我们提出从 [m] 到 [n] 的函数集的双次线性 IPP，其中每个值要么出现 m/k 次，要么根本不出现：对于每个 α ∈ (0, 1/3)，验证者的查询复杂度为 poly(1/ε) · k^{(2/3)−2α}，证明者的查询复杂度为 poly(1/ε) · e^{O(k^{(2/3)+α})}。相比之下，在这两种情况下，众所周知，分布的相应属性不具有双效 IPP（参见 Herman 和 Rothblum，2025）。实际上，第一个属性