Counting circuits with constraints

Question

Please forgive me if this question is trivial, I couldn’t come up with an answer (nor finding one).

In order to show that there are boolean functions $f : \{0,1\}^n \rightarrow \{0,1\}$ which can be computed only using circuits of size $\Omega(2^n/n)$, we use a counting argument: there are at most $O(2^{k \log k})$ circuits of size $k$, and $2^{2^n}$ such functions.

Suppose that I am interested in counting circuits of size $k$ that compute different functions. The "simple" counting argument won't work since it may be possible that two "syntactically" different circuits actually compute the same function. In other words, I want to bound the size of the set: $$F = \{ f: \{0,1\}^n \rightarrow \{0,1\} | f \text{ can be computed using a circuit of size }k \} $$

Then $|F| < $ the number of circuits of size $k$ (since any circuit computes one function), but how can I bound $|F|$ from below? (i.e. $ x <|F|$)

Answer 1

In order to bound the number of functions computed by circuits of size $k$, you have at least two options:

• Construct a large number of circuits of size $k$, which by construction compute different functions.
• Consider a natural probability distribution on circuits of size $k$, and estimate the probability that two random circuits compute the same function.

As an example, it is known that every function on $m$ variables can be computed by a circuit of size $O(2^m/m)$. By considering functions of the form $f_1(x_1,\ldots,x_m) \lor \cdots \lor f_{n/m}(x_{n-m+1},\ldots,x_n)$, this shows that there are at least $(2^{2^m})^{n/m}$ different functions computed by circuits of size $k = O(n2^m/m^2)$. In terms of $k$, the number of functions is roughly exponential in $k\log k$, for $m \gg \log n$.