## 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.