Junta Correlation is Testable
Junta Correlation is Testable
复制标题
DOI：
10.1109/focs.2019.00090
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Anindya De;Elchanan Mossel;Joe Neeman
中科院分区：
文献类型：
--
作者：
Anindya De;Elchanan Mossel;Joe Neeman
耐受的术语测试的问题是一个自然而具有挑战性的问题，它询问函数的属性是否具有与K-Junta的指定相关性的属性。在本文中，我们对此问题给出了一个肯定的答案：有一种算法给出了距离参数C，D和Oracle访问HyperCube上布尔函数f的算法，具有查询复杂性Exp（k）.poly（1/（c-d）（c-d） ））并区分以下情况：1。f与任何k-junta的距离至少为c； 2。有一个k-junta g，最多距离f。这是第一个非平凡测试仪（即查询复杂性独立于环境尺寸n），它适用于所有C和D（由0.5界）。 Blais等人的最佳先前已知结果，要求C至少为16D。实际上，凭借相同的查询复杂性，我们实现了确定最相关的K-Junta的更强大目标，直到坐标排列。我们可以进一步提高（k/（c-d））的查询复杂性，以区分以下情况的（较弱）任务：1。f与任何k'-junta的距离至少为c。 2。有一个k-junta g，它最多与f。这里k'= poly（k/（c-d））。我们的主要工具是基于傅立叶分析的算法，这些算法模拟了Oracle访问函数的有影响力坐标。
The problem of tolerant junta testing is a natural and challenging problem which asks if the property of a function having some specified correlation with a k-Junta is testable. In this paper we give an affirmative answer to this question: There is an algorithm which given distance parameters c, d, and oracle access to a Boolean function f on the hypercube, has query complexity exp(k).poly(1/(c-d)) and distinguishes between the following cases: 1. The distance of f from any k-junta is at least c; 2. There is a k-junta g which has distance at most d from f. This is the first non-trivial tester (i.e., query complexity is independent of the ambient dimension n) which works for all c and d (bounded by 0.5). The best previously known results by Blais et~al., required c to be at least 16d. In fact, with the same query complexity, we accomplish the stronger goal of identifying the most correlated k-junta, up to permutations of the coordinates. We can further improve the query complexity to poly(k/(c-d)) for the (weaker) task of distinguishing between the following cases: 1. The distance of f from any k'-junta is at least c. 2. There is a k-junta g which is at a distance at most d from f. Here k'=poly(k/(c-d)). Our main tools are Fourier analysis based algorithms that simulate oracle access to influential coordinates of functions.