For a function $f:\{0,1\}^n \rightarrow \{0,1\}^m$, let $C(f)$ be the circuit complexity (for concreteness, constants and NOT gates are free, while 2-input AND gates cost 1).

Let $k{\times}f : \{0,1\}^{kn} \rightarrow \{0,1\}^{km}$ be the function which computes $k$ copies of $f$ on independent inputs, so $k{\times}f(x_1, ..., x_{kn}) = (f(x_1, ..., x_n), ..., f(x_{(k-1)n+1}, ..., x_{kn}))$. For instance, $2{\times}{\oplus}(x,y,z,w) = (x\oplus y, z\oplus w)$.

Define the asymptotic mass production complexity of $f$ to be $C_a(f) = \lim_{k\rightarrow\infty} \frac{C(k{\times}f)}{k}$ (since $C(k{\times}f)$ is a subadditive function of $k$, the limit always exists and is equal to the $\inf$). For example, it's possible to show that $C_a(\oplus) = C(\oplus) = 3$. A less trivial example is given by random linear functions: if $f : \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$ is a random linear function, then $C(f) = \Omega(\frac{n^2}{\log(n)})$ by a standard counting argument, while $C_a(f) \le \frac{C(n{\times}f)}{n} = O(n^{\omega_2-1})$, where $\omega_2 \le \log_2(7)$ is the matrix multiplication constant for $\mathbb{F}_2$.

My question: Can we prove that for any $f : \{0,1\}^n \rightarrow \{0,1\}^m$, we always have $C_a(f) = O(n+m)$?

There is an easy construction based on sorting networks that shows that $C_a(f) = O(n(n+m))$ - this is off by a factor of $n$ from what I want. In fact, I'll show that $C(2^n{\times}f) = O(n(n+m)2^n)$:

Given $2^n$ input strings $v_0, ..., v_{2^n-1}$ each of length $n$, for each $i < 2^n$ we make a string $X_i$ of length $n+m+1$ by putting $m+1$ $0$s at the end of each $v_i$, and we make a string $Y_i$ of the same length by first encoding $i$ with $n$ binary bits, following this with a $1$, and filling the last $m$ bits with $f(i)$ ($i$ considered as a string of $n$ bits). Then we sort the combined list of $X_i$s and $Y_i$s using a sorting network, keeping track of the result of each comparison - this requires $O(n2^n)$ comparisons, and $O(n+m)$ gates per comparison. After sorting, each $X_i$ is either next to an identical $X_{i'}$ or to some $Y_j$ with $v_i = j$ and with last $m$ bits $f(j) = f(v_i)$, and we can use the $n+1$st bit of each string to tell whether we are looking at an $X_i$ or a $Y_j$. So now we propagate the values $f(v_i)$ to the left with $O(m2^n)$ gates (or if we prefer low-depth circuits, with $n$ layers of $O(m2^n)$ gates using power-of-2 shenanigans). Finally, we unsort, using our record of the comparisons we kept track of during the sorting process, to route each answer to the relevant output gate.

It's plausible that this construction could be improved by using a sorting method which is not based on comparisons, but then I don't see how to unsort at the end. Edit: To unsort at the end, we just need to modify the beginning of the strategy by appending $i$ to the end of each $X_i$, making all the strings have length $2n+m+1$, and then finish by sorting based on the last $n$ bits. I tried searching the literature, and eventually found this paper which says in the abstract that improving the circuit complexity of sorting to $o(n(n+m)2^n)$ is an open problem.

  • $\begingroup$ See section 10.2 in Wegener's book: eccc.weizmann.ac.il/resources/pdf/cobf.pdf $\endgroup$
    – Or Meir
    Sep 15, 2018 at 4:11
  • $\begingroup$ @OrMeir If you are referring to Uhlig's bound (Theorem 2.3 of that book), as stated there it isn't strong enough to even prove that C_a(f) is at most 2^{n/2}. The issue is that the number of repetitions considered there is subexponential, so the per-copy savings are subexponential as well. $\endgroup$
    – zeb
    Sep 15, 2018 at 6:40


Your Answer

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