Also rejecting 1

At the end of class we considered running Håstad's test with $\delta = .75 \epsilon$ many times - $O(1/\epsilon^2)$ to be precise - and then accepting iff the empirical fraction of passes was at least $1 - .8 \epsilon$. We saw that this gave a test for the class {${\chi_S : |S| \leq 1}$}. I asked how we could also reject functions close to the $1$ function, but hurried over the explanation.

Aaron's suggestion was a very good one since we can do it making zero additional queries. Look at all the $f(x)$'s and $f(y)$'s we queried (not the $f(z)$'s) and reject also if the fraction of times the answer was 1 is at least $3/4$. Note that all the $x$'s and $y$'s are independent random strings.

Now certainly dictators (which are half 1, half -1) will pass this extra test except with exponentially small probability in $\epsilon$, so their acceptance probability, if it was at least $2/3$ before, is at least $.66$ now (which is fine).

On the other hand, suppose $f$ is $\epsilon$-far from the set of dictators. Then it's also $\epsilon$-far from the set {dictators} $\cup$ $\{1\}$ (and so the Håstad tests will reject it with probability at least $2/3$) unless it's $\epsilon$-close to $1$. But in this case, the additional test will reject except with exponentially small probability in $\epsilon$, so we're again fine.


The alternate fix I suggested involved using local decodability of parity functions. After all the Håstad tests, if we still haven't rejected then (with probability at least $2/3$) $f$ is $\epsilon$-close to either $1$ or a dictator function - in particular, to a linear function. Now use 2 more queries to do local decoding on the string $(-1, -1, ..., -1)$, and reject if the answer is 1. Dictators will pass this with probability at least $1-2\epsilon$, so overall they pass with probability at least $2/3 - 2\epsilon$ which is large enough (assuming $\epsilon < .01$ now, say). And any function $\epsilon$-close to being $1$ will pass this with probability at most $2\epsilon$, so overall it will pass with probability at most $1/3 + 2\epsilon$, again fine.

Two good exercises for you:

1. Understand why it is without loss of generality to assume $\epsilon < .01$.

2. In the local decoding of $(-1,-1, ..., -1)$ we are really doing the following 2-query test: Pick $y$ at random, and accept iff $f(y) \neq f(-y)$. Express the probability that this test passes in terms of the Fourier coefficients of $f$.