6
$\begingroup$

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?
$\endgroup$
  • 5
    $\begingroup$ 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}$. $\endgroup$ – Pål GD Apr 23 '15 at 1:53
9
$\begingroup$

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.

$\endgroup$

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.