Existence of boolean function with exponential average case hardness

Question

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.

Answer 1

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}$.