1
$\begingroup$

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.

$\endgroup$
15
  • $\begingroup$ Can you state precisely what you are trying to show? $\endgroup$ – Yuval Filmus Nov 9 '20 at 13:33
  • $\begingroup$ 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. $\endgroup$ – roydiptajit Nov 9 '20 at 14:22
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 9 '20 at 14:24
  • $\begingroup$ 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)$. $\endgroup$ – roydiptajit Nov 9 '20 at 14:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Nov 9 '20 at 14:37
1
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ $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.. $\endgroup$ – roydiptajit Nov 9 '20 at 19:12
  • $\begingroup$ One doubt, what was wrong in my approach using chernoff bound? $\endgroup$ – roydiptajit Nov 10 '20 at 6:44
  • $\begingroup$ Nothing wrong. All these bounds are the same. You just never carried your plan through. $\endgroup$ – Yuval Filmus Nov 10 '20 at 6:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.