Quasirandom Boolean Function

A function is -quasirandom if for every of size , and every

In the notation of Averaging Projection

Intuition

Knowing what any coordinates of are gives almost no information to what is going to be.

Lemma

For every , and there is some such that if for some monotone and is -quasirandom then

(actually for )

Proof

Suppose that

By the mean value theorem there is some such that

By Margulis-Russo Formula it follows

By the -biased Friedgut Junta Theorem we can find a boolean -Junta such that

and . But

by monotonicity of so

and

Choosing find

Consider the set . Then

so there is some such that Then

so by monotonicity of we get

so taking we find

contradicting quasirandomness.