# Existence of boolean function with exponential average case hardness

Show that for every large enough $$n$$, there is a boolean function $$f\colon \{0,1\}^n\longrightarrow\{0,1\}$$, whose average case hardness is exponential. The question is taken from Arora Barak Computational Complexity textbook, Chapter-16, Ex-3.

Average case hardness of a boolean function $$f$$ is defined as, the largest $$S(n)$$ s.t. for all circuit $$C_n\in \operatorname{Size}(S(n))$$, $$\Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$$. Here $$U_n$$ is uniform distribution over $$\{0,1\}^n$$. I want to show there are boolean functions having $$S(n)$$ exponential in $$n$$. My approach is to pick a random $$f$$ and show via Chernoff bound, the probability of having such function is $$>0$$.

Formally, I am following this approach, I need to show, $$\Pr_{x\in U_n}[C_n(x)=f(x)]-1/2<1/2^n$$, $$S(n)=2^n$$ . Take $$Y$$ another random variable, $$Y=1$$ iff, $$C_n[x]=f[x]$$ else $$0$$. I express $$\Pr_{x\in U_n}[C_n(x)=f(x)]=\frac{1}{2^n}\sum Y_i$$, Now, by Chernoff bound if I can bound the probability $$\Pr[\frac{1}{2^n}\sum Y_i-1/2]>1/2^n$$ over $$C$$, I can take the union bound over all $$C$$ to show that probability is less than $$1$$. But, I am not sure if I can replace $$\mu$$ of Chernoff bound with any constant like $$1/2$$.

Is my approach correct? Can anyone help with my query? $$U_n$$ is uniform distribution.

• Can you state precisely what you are trying to show? Nov 9, 2020 at 13:33
• Using chernoff bound, I want to show that the probability of random $f$, having exponential average case hardness is $>0$, thus it exists, but that needs $\mu$ in chernoff bound to be replaced by $p$. I am not quite sure if I am following the correct approach here. Nov 9, 2020 at 14:22
• Can you state precisely what you are trying to show? I have no idea what you mean by "exponential average case hardness". Try to be explicit. Nov 9, 2020 at 14:24
• Average case hardness of a boolean function is defined as, the largest $S(n)$ s.t. for all circuit $C_n\in Size(S(n))$, $Pr_{x\in U_n}[C_n(x)=f(x)]<1/2+1/S(n)$. Here $U_n$ is uniform distribution over $\{0,1\}^n$. I want to show there are functions with exponential $S(n)$. Nov 9, 2020 at 14:36
• Instead of answering in the comments, please update your question. Don't add an "EDIT:" paragraph. Instead, just update the wording of your question to contain the necessary information. Nov 9, 2020 at 14:37

Let $$C$$ be a fixed function, and let $$f$$ be a random function. For $$z \in \{0,1\}^n$$, let $$X_z = 1$$ if $$C(z) = f(z)$$, and $$X_z = -1$$ otherwise. Thus $$2^{-n} \sum_z X_z = \Pr[C(z) = f(z)] - \Pr[C(z) \neq f(z)] = 2\Pr[C(z) = f(z)] - 1.$$ Therefore $$\Pr[C(z) = f(z)] \geq 1/2+\delta$$ iff $$2^{-n} \sum_z X_z \geq 2\delta$$. According to Bernstein's inequality, $$\Pr\left[2^{-n} \sum_z X_z \geq 2\delta\right] \leq \exp \left(-\frac{42^n\delta^2}{2(1+2\delta/3)}\right) \leq e^{-2^n\delta^2}.$$ (The true exponent is more like $$-2^{n+1}\delta^2$$.)
The number of (de Morgan) circuits of size $$s$$ is at most roughly $$e^{2s\log s}$$ (according to notes of Trevisan; the bound is not tight). According to the union bound, the probability (over $$f$$) that some circuit $$C$$ of size $$s$$ satisfies $$\Pr[C(z) = f(z)] \geq 1/2+\delta$$ is at most $$e^{2s\log s} \cdot e^{-2^n\delta^2}$$. If $$2s\log s < 2^n\delta^2$$ then this probability is less than $$1$$, and so there exists some function $$f$$ such that $$\Pr[C(z) = f(z)] < 1/2+\delta$$ for all circuits of size $$s$$.
You're interested in the setting $$\delta = 1/s$$. The argument works as long as $$2s^3\log s < 2^n$$, and in particular, when $$s\approx2^{n/3}$$.
• $Pr[2^{-n}\sum_zX_z\geq2\delta]\leq e^{-2^n\delta^2}\leq 2^{-2^n\delta^2}$, so we can replace de morgan circuits with any boolean circuit where the number of circuits of size $S$ becomes $2^s(2+2log(S))$. This also works I think. Thanks for your help.. Nov 9, 2020 at 19:12