Friedgut Junta Theorem

Let be a function on the -Biased Cube. Suppose that

Then there exists an -Junta with

and

Proof

Let (to be chosen later) and let

Let Now note

by the Bonami Lemma. Also note

by the fact that so we can write

Use the definition of Influence to find:

and thus

Now let

Then

By the hypothesis, the second term is . Also

Therefore

so set

Corollary

We can approximate by a boolean -Junta .

Proof

Take