# Existence of boolean function with exponential average case hardness

Computer Science Asked by Diptajit Roy on November 15, 2020

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.

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

Correct answer by Yuval Filmus on November 15, 2020

## Related Questions

### Calculating the structural integrity of a pixel grid

1  Asked on September 27, 2020 by jugbot

### Fill the time slot with the best match

1  Asked on September 18, 2020 by ras

### SQL query question

0  Asked on July 27, 2020 by breta-kapedani

### In the dataflow programming paradigm programs are modeled as directed graphs. Are the edges of the graph variables? And are the vertexes functions?

1  Asked on July 27, 2020 by q-p

### Count Unique Subsequences to Destination?

0  Asked on July 25, 2020 by hcsf