Learning juntas

The junta-learning problem is: You have access to uniform-distribution random examples from a function $f:\{-1,1{\}}^n\to \{-1,1\}$ that is promised to depend only on some subset of $r$ of the variables. Think of $r$ as $\log n$, or even just a large constant. The task is to determine the $r$ relevant variables in time substantially better than $n^r$.

For more on this problem, see Section 2 of this collection of open problems, written by Avrim Blum.

In class tomorrow we will see an algorithm that finds the variables in time roughly $n^{.704r}$. As stated in Avrim's note, if you can improve this to just $n^{.666r}$, he'll give you $ 100. If you can improve it to $n^{O\left(1\right)}$ for $r=\log n$, he'll give you $ 1000!

Fourier analysis. It can be lucrative.