Hastad Dictator Test for Boolean Functions
A function \(f\colon \{0,1\}^n\to \{0,1\}\) is a dictator function if there exists \(i\in [n]\) such that \(f(x) = x_i\). That is, the function is completely determined by its \(i\)-th input.
A function \(f\colon \{0,1\}^n\to \{ \pm 1\}\) is a dictator function if there exists \(i\in [n]\) such that \(f(x) = (-1)^{x_i}\). Dictator functions are just characteristic function for singletons \(\chi_i \equiv \chi_{\{i\}} = (-1)^{x_i}\).
Hastad dictator test is defined as follows:
- Pick up \(x,y \in\{0,1\}^n\) uniformly and independently.
- Pick up \(w \in\{0,1\}^n\) by independently choosing each \(w_i\) to be 1 with probability \(p\).
- Accept if and only if \(f(x+y+w) = f(x)f(y)\).
Lemma. For any \(f\colon \{0,1\}^n\to \{\pm 1\}\), the probability that Hastad dictator test accepts is
\[
\frac{1}{2} + \frac{1}{2} \sum_{\alpha} (1-2p)^{|\alpha|} \widehat{f}(\alpha)^3,
\]
where \(\alpha\in\{0,1\}^n\) and \(|\alpha| = \sum_i \alpha_i\).
Proof. Let \(z = x+y+w\). The probability that Hastad test accepts equals
\[
\frac{1}{2} + \frac{1}{2} E[f(x)f(y)f(z)].
\]
Then we have the following:
\begin{eqnarray*}
E[f(x)f(y)f(z)]
&=& E\left[ \sum_{\alpha,\beta,\gamma} \widehat{f}(\alpha) \widehat{f}(\beta) \widehat{f}(\gamma) \chi_\alpha(x)\chi_\beta(y)\chi_\gamma(z) \right] \\
&=& \sum_{\alpha,\beta,\gamma} \widehat{f}(\alpha) \widehat{f}(\beta) \widehat{f}(\gamma) E[ \chi_\alpha(x)\chi_\beta(y)\chi_\gamma(x+y+w) ] \\
&=& \sum_{\alpha,\beta,\gamma} \widehat{f}(\alpha) \widehat{f}(\beta) \widehat{f}(\gamma) E[ \chi_{\alpha+\gamma}(x)\chi_{\beta+\gamma}(y) \chi_{\gamma}(w) ] \\
&=& \sum_{\alpha,\beta,\gamma} \widehat{f}(\alpha) \widehat{f}(\beta) \widehat{f}(\gamma) E[ \chi_{\alpha+\gamma}(x)] E[\chi_{\beta+\gamma}(y) ]E[\chi_{\gamma}(w) ] \\
\end{eqnarray*}
Since \(E_x[\chi_\alpha(x)]\) is 0 if \(\alpha \neq 0\) and 1 otherwise, each item in the summation above is non-zero if and only if \(\alpha = \beta=\gamma\). We also have
\[
E[\chi_{\gamma}(w) ] = \prod_{i}^n E[ (-1)^{\gamma_i w_i} ] = (1-2p)^{|\gamma|}.
\]
Therefore,
\[
E[f(x)f(y)f(z)] = \sum_{\alpha} (1-2p)^{|\alpha|} \widehat{f}(\alpha)^3.
\]
This ends the proof.
The factor \((1-2p)^{|\alpha|}\) decades exponentially, which means large \(\alpha\) contribute less to the summation, and small \(\alpha\) contribute more.
If \(f\) is a dictator function, then there is only one \(\alpha\) such that \(\widehat{f}(\alpha)\) is nonzero, and we have \(|\alpha| = 1\) and \(\widehat{f}(\alpha) = 1\) . Then the probability that \(f\) passes the test is
\[
\frac{1}{2} + \frac{1}{2} (1-2p) = 1 – p.
\]
If a function \(f\) passes the test with probability \(1-\epsilon\), then
\[
1-\epsilon \leq \frac{1}{2} + \frac{1}{2} \sum_{\alpha} (1-2p)^{|\alpha|} \widehat{f}(\alpha)^3,
\]
\[
1-2\epsilon \leq \sum_{\alpha} (1-2p)^{|\alpha|} \widehat{f}(\alpha)^3
\leq \max_{\alpha}(1-2p)^{|\alpha|} \widehat{f}(\alpha).
\]
Suppose we pick \(\epsilon = p\), then for all \(\alpha\) with \(|\alpha|\geq 2\), we have \(1-2\epsilon > (1-2p)^{|\alpha|}\). Thus there must be some \(\alpha\) with \(|\alpha|\leq 1\) such that either (1) \(|\alpha|=1\) and \(\widehat{f}(\alpha) = 1\), or \(|\alpha|=0\) and \(\widehat{f}(\alpha) \geq 1-2\epsilon\). That is, \(f\) is either a dictator function or close to a constant function.