Junta correlation is testable

by Anindya De, Elchanan Mossel, and Joe Neeman.

Oded's comments

I missed a prior announcement of this interesting work, which provides an algorithm for approximating the distance of an input function (given via oracle access) to a k-junta. Since the focus is on additive error approximation, this is the same as approximating the maximum correlation of the input function with a k-junta. The techniques include (21) constructing a list of oracles that return the values of individual variables that have sufficiently high influence on the input function (i.e., a typical oracle is associated with bit location $i$ and on input $x$ returns $x_i$, whereas $i$ remains unknown); and (2) using random restriction to reduce a problem about general $k$ to the case $k=3D1$.

The original abstract

A Boolean function f on the n-dimensional hypercube is said to be a k-junta if it is dependent only on some k coordinates of the input. These functions have been widely studied in the context of PCPs, learning theory and property testing. In particular, a flagship result in the last area is that k-juntas can be tested with \tilde{O}(k) queries -- i.e., there is an algorithm which when given a black box to f, makes only \tilde{O}(k) queries and decides between the following two cases: f is a k-junta, and f is at least 0.01 far from every k-junta g in Hamming distance. Surprisingly, the query complexity is completely independent of the ambient dimension n.

In this work, we achieve the same qualitative guarantee for the noise tolerant version of this problem. In particular, we give a 2^k query algorithm to distinguish between the following two cases. 1. f is at most 0.48 far from some k-junta. 2. f is at least 0.49 far from every k-junta. The algorithm and its proof of correctness are simple and modular employing some classical tools like "random restrictions" with elementary properties of the noise operator on the cube.

Back to list of Oded's choices.