3
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.