Anindya De: Junta correlation is testable.

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 property testing 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:
1. f is a k-junta.
2. 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  0.48-close to 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.

Joint work with Elchanan Mossel and Joe Neeman.