Junta correlation is testable

by Anindya De, Elchanan Mossel, and Joe Neeman.

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