Testing Juntas Nearly Optimally
April 15, 2009
A function on n variables is called a $k$-junta if it depends on at most $k$ of its $n$ variables. In this talk, we study the problem of testing $k$-juntas. An algorithm for testing $k$-juntas is allowed to query the value of the function on a small number of inputs and must then distinguish between functions that are $k$-juntas and functions that are "far" from being $k$-juntas.

Prior to the current work, the best known algorithm for testing $k$-juntas required $O(k^{1.5})$ queries to the function. In this talk, we introduce a new algorithm for testing $k$-juntas with only $O(k \log k)$ queries. This result is optimal, up to a logarithmic factor.

A key component of the analysis of the algorithm is a new structural result on juntas. Roughly, we show that if a function $f$ is "far" from being a $k$-junta, then $f$ is also "far" from determinable by $k$ parts in a random partition of the function's input variables. The tools used in the analysis of the algorithm include Fourier analysis, the influence of variables, and the Efron-Stein decomposition of functions.