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:\mid S\mid \le 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\left(x\right)$'s and $f\left(y\right)$'s we queried (not the $f\left(z\right)$'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$ $\left\{1\right\}$ (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 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 .

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\left(y\right)\ne f(-y)$. Express the probability that this test passes in terms of the Fourier coefficients of $f$.