Partially Symmetric Functions Are Efficiently Isomorphism-Testable
Partially Symmetric Functions Are Efficiently Isomorphism-Testable
复制标题
DOI：
10.1137/140971877
复制
发表时间：
2011-12
期刊：
影响因子：
--
通讯作者：
Eric Blais;Amit Weinstein;Yuichi Yoshida
中科院分区：
文献类型：
--
作者：
Eric Blais;Amit Weinstein;Yuichi Yoshida
给定一个布尔函数 f，f 同构测试问题需要一种随机算法来区分与 f 相同的函数，直到重新标记输入变量与远非如此的函数。属性测试中一个重要的开放问题是确定对于哪些函数 f 我们可以使用恒定数量的查询来测试 f 同构。尽管最近人们对这个问题给予了很多关注，但实际上只有两类函数已知可以有效地进行同构测试：对称函数和 juntas。我们通过证明所有部分对称函数（除了恒定数量的变量之外对所有变量的重新排序不变的函数）来统一和扩展这些结果，都是有效的同构可测试的。这类函数由香农首先提出，包括对称函数、juntas 和许多其他函数。我们推测这些函数本质上是唯一可有效同构测试的函数。为了证明我们的主要结果，我们还表明部分对称性是可以有效测试的。反过来，为了证明这个结果，我们必须重新审视军政府测试问题。我们提供了近乎最优的军政府测试器的正确性的新证明。我们的新证明用纯粹的组合论证取代了原始证明的傅里叶机制，该论证利用了低影响力和交叉族的变量集之间的联系。我们证明中的另一个重要组成部分是对称影响的新概念。我们使用这种影响度量来证明部分对称性是有效可测试的，并且还为部分对称函数构建了一个有效的样本提取器。然后，我们将样本提取器与隐式学习测试方法相结合，以完成部分对称函数可有效同构测试的证明。
Given a Boolean function f, the f-isomorphism testing problem requires a randomized algorithm to distinguish functions that are identical to f up to relabeling of the input variables from functions that are far from being so. An important open question in property testing is to determine for which functions f we can test f-isomorphism with a constant number of queries. Despite much recent attention to this question, essentially only two classes of functions were known to be efficiently isomorphism testable: symmetric functions and juntas. We unify and extend these results by showing that all partially symmetric functions -- functions invariant to the reordering of all but a constant number of their variables -- are efficiently isomorphism-testable. This class of functions, first introduced by Shannon, includes symmetric functions, juntas, and many other functions as well. We conjecture that these functions are essentially the only functions efficiently isomorphism-testable. To prove our main result, we also show that partial symmetry is efficiently testable. In turn, to prove this result we had to revisit the junta testing problem. We provide a new proof of correctness of the nearly-optimal junta tester. Our new proof replaces the Fourier machinery of the original proof with a purely combinatorial argument that exploits the connection between sets of variables with low influence and intersecting families. Another important ingredient in our proofs is a new notion of symmetric influence. We use this measure of influence to prove that partial symmetry is efficiently testable and also to construct an efficient sample extractor for partially symmetric functions. We then combine the sample extractor with the testing-by-implicit-learning approach to complete the proof that partially symmetric functions are efficiently isomorphism-testable.