Regularity Lemma for Boolean Functions

For every there exists such that for every on -Biased Cube there exists with such that if is chosen randomly from then the probability that is a -Quasirandom Boolean Function is at least .

Proof

Suppose that doesn’t satisfy the conclusion of the lemma. Let and . If is not a -Quasirandom Boolean Function, then there is some with and some such that

Let . If we choose a random element of then it equals with probability Therefore:

Also note that

so LHS is the variance of over random . As is constant here, this variance has to be equal to

so

in this case. Let

where the union is over all such that is not a -Quasirandom Boolean Function. We conclude

Now note that a random has probability at least to satisfy the above. Also Mean Square Density satisfies for any :

Thus averaging over all we get:

i.e.

Now do an iteration. Start with . At -th stage, if doesn’t work, replace it with using such that

Thus the process must eventually terminate (as we cannot exceed )

Remark

The bound on is horrible. We can only get .