# Is there an intuitive proof for the existence of hard functions?

I am referring to the theorem on page 115 of the book by Arora and Barak, which states that, For every $n>1$, there exists a function $f:\{0,1\}^n \rightarrow \{0,1\}$ that cannot be computed by a circuit $C$ of size $\frac{2^n}{10n}$"

• Can someone give a more intuitive proof of this than the one presented there?

For example he proof there at one point claims with little justification that there are at most $2^{0.92^n}$ circuits of size at most $\frac{2^n}{10n}$. Why? I couldn't reproduce this 0.92" thing!

• It seems that one even improve this theorem to higher lower bound of $\frac{2^n}{n}$. Can someone kindly help do that? How much up can one get this?
• The crux of the proof is that there are $2^{2^n}$ functions, but only $2^{9S \log S}$ circuits. Let $S = \frac{2^n}{10n}$ and expand to get that the number of circuits is strictly lower than $2^{2^n}$. Apr 23, 2015 at 1:53

As Pål GD mentions in his comment, the proof is actually very simple: there are $2^{2^n}$ functions, but only $C_S = S^{O(S)}$ circuits of size at most $S \geq n$. The exact constant in the exponent depends on the exact definition of a circuit. Getting the best exponent requires some rather intricate arguments, together with the assumption $S = \omega(n)$. We then compute the maximal $S$ such that $C_S < 2^{2^n}$, and conclude that there must be a function that cannot be computed by a circuit of size at most $S$. The answer is $S = O(2^n/n)$, and we usually really don't care about the hidden constant; we tend to abstract away constants in complexity theory.
The same argument shows, with very small modifications, that a random function has circuit complexity $\Omega(2^n/n)$ in expectation and with high probability.
How about an explicit function with complexity $\Omega(2^n/n)$? This is a difficult open problem. The best lower bounds we have for explicit functions are $\Omega(n^3)$ for Andreev's function (see Komargodski–Raz–Tal for the best result in this direction). I am told that obtaining anything better than $\Omega(n^3)$ would be difficult due to the natural proof barrier.