Circuit size of a random two to one function

Question

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.

Answer 1

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.