# Circuit size of a random two to one function

Consider the set of all possible two-to-one functions that map inputs from $$\{0, 1\}^{n}$$ (domain) to outputs in $$\{0, 1\}^{m}$$ (co-domain) and let $$m > n$$.

If I pick a function randomly from this set, what is the probability that it can be computed by a Boolean circuit of size $$\text{poly}(m)$$?

Note that while the co-domain of the set of functions so defined is $$\{0, 1\}^{m}$$. However, the range of each individual function is a set of size $$2^{n-1}$$. What that set looks like depends on what function we randomly pick.

I was thinking of using a counting argument here. Let $$M = 2^{m}$$ and $$N = 2^{n}$$. Then, the number of two-to-one functions is given by $$\frac{N!}{2^{N/2}}\times {M \choose N}.$$The number of circuits (made of AND, OR, and NOT gates) of size $$k$$ is at most $$2^{k^{2}} \times 3^{k}.$$

In general, in the asymptotic limit, the second expression is larger than the first expression -- which would indicate that, perhaps, all two-to-one functions can have polynomial sized circuit description.

However, not every circuit computes a two-to-one function. So, this does not tell me what fraction of two-to-one functions has polynomial sized circuits.

Every function $$f\colon \{0,1\}^n \to \{0,1\}^m$$ can be computed by a bounded fan-in circuit of size $$O(2^n m)$$, which is polynomial in $$m$$ iff $$m$$ is exponential in $$n$$:
• First, for every $$k \leq n$$ and for every $$y \in \{0,1\}^k$$, we compute a gate $$g(y)$$ which expresses $$x_1 = y_1 \land \cdots \land x_k = y_k$$. This can be done recursively.
• Then, we compute the outputs using the formula $$f_i(x) = \bigvee_{f_i(y) = 1} g(y).$$
This can likely be improved to $$O(\frac{2^n}{n} m)$$ using standard tricks.
On the lower bound side, I claim that the first bit $$f_1$$ of a random two-to-one function is already quite complex, requiring bounded fan-in circuits of size $$\Omega(2^n/n)$$. We can choose $$f$$ by first choosing its image (a choice of $$2^{n-1}$$ strings out of $$2^m$$), listing the image repeated twice, and then permuting the list at random. It is likely the the initial choice results in a balanced first bit (roughly half the strings start with $$0$$, and roughly half start with $$1$$). After permuting the list, we can choose a random function $$f\colon \{0,1\}^n \to \{0,1\}$$ with specified bias (i.e., $$\Pr[f=1]$$), where the bias is itself a random variable concentrated around $$1/2$$. This should imply the claimed lower bound using the standard counting argument; for example, if the bias is exactly $$1/2$$, then instead of the usual $$2^{2^n}$$ functions we have $$\Theta(2^{2^n}/2^{n/2})$$ out of which we choose one at random, which is not a big difference from this perspective.