**not**necessarily quasirandom.

If you want to think about it, you may be able to convince yourself that the function $f(x) = "x_1 \oplus$ Majority$(x_2, ..., x_n)"$ has $o(1)$ correlation with every function on $o(\sqrt{n})$ bits, and yet it is not even $(.3,.3)$-quasirandom!

So the property of having low correlation with every small junta is

*weaker*then our notion of being quasirandom. As it happens, the legit hardness of approximation for 3Lin result (without using UGC) uses the fact that that even functions with this weaker property are rejected by the H{\aa}st-Odd test with probability close to $1/2$.

## No comments:

Post a Comment