Noise-Resistant Boolean-Functions are Juntas
Guy Kindler, Muli Safra · 2003
We consider Boolean functions over n binary variables, and a general p-biased, product measure over the inputs. We show that if f is of low-degree, that is, so that the weight of f on the Fourier-Walsh products of size larger than k is small, then f is close to a junta, namely, a function which depends only on very small, related to k however unrelated to n, number of variables. We conclude that juntas are the only highly noise-resistant Boolean functions. Furthermore, we manage to utilize such a statement to prove an alternative switching lemma, one which may prove useful in the study of computational-complexity lower-bounds, in particular to a completely analytical proof that any AC function is close to low-degree.