# 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.