Existence of boolean function with exponential average case hardness

Question

Show that for every large enough $n$, there is a boolean function $fcolon {0,1}^nlongrightarrow{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_nin operatorname{Size}(S(n))$, $Pr_{xin 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_{xin 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_{xin 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.

circuits lower bounds

Yuval Filmus · Accepted Answer

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)] = 2Pr[C(z) = f(z)] - 1.
$$
Therefore $Pr[C(z) = f(z)] geq 1/2+delta$ iff $2^{-n} sum_z X_z geq 2delta$. According to Bernstein's inequality,
$$
Prleft[2^{-n} sum_z X_z geq 2deltaright] leq exp left(-frac{42^ndelta^2}{2(1+2delta/3)}right) leq e^{-2^ndelta^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^{2slog 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^{2slog s} cdot e^{-2^ndelta^2}$. If $2slog s < 2^ndelta^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^3log s < 2^n$, and in particular, when $sapprox2^{n/3}$.

Existence of boolean function with exponential average case hardness

One Answer

Add your own answers!

Ask a Question