Are there known to exist functions with the following direct-sum property?

Question

This question can be asked either in the framework of circuit complexity of Boolean circuits, or in the framework of algebraic complexity theory, or probably in lots of other settings. It is easy to show, by counting arguments, that there exist Boolean functions on N inputs that require exponentially many gates (though of course we don't have any explicit examples). Suppose I wish to evaluate the same function M times, for some integer M, on M distinct sets of inputs, so that the total number of inputs is MN. That is, we just want to evaluate $f(x_{1,1},...,x_{1,N}), f(x_{2,1},...,x_{2,N}),...,f(x_{M,1},...,x_{M,N})$ for the same function $f$ at each time.

The question is: is it known that there exists a sequence of functions $f$ (one function for each N) such that, for any N, for any M, the total number of gates required is at least equal to M times an exponential function of N? The simple counting argument does not seem to work since we want this result to hold for all M. One can come up with simple analogues of this question in algebraic complexity theory and other areas.

Answer 1

Well, that is false: it is possible to evaluate M copies of ANY f using only O(N(M+2^N)) gates which can be much less than M*exp(N) (in fact, you get linear amortized complexity for exponential M). I don't remember a reference, but I think that it can go something like the following:

First add 2^N fictitious inputs which are just constants 0...2^N-1 and now denote the i'th N-bit input by xi (so for i<=2^N we have xi=i, and for 2^N < i <=2^N+M we have the original inputs). Now we create a triplet for each of the M+2^N inputs: (i,xi,fi) where fi is f(i) for the first 2^N inputs (a constant that is hardwired into the circuit) and fi="*" otherwise. Now we sort the triplets (i,xi,fi) according to the key xi, and let the j'th triplet be (i_j,x_j,f_j) from this we compute a triplet (i_j,x_j,g_j) by letting g_j be f_j if f_j is not a "*" and let g_j be g_(j-1) otherwise. Now sort the new triplets back according to the key i_j, and you got the correct answers at the correct places.

Answer 2

There’s another result that further constrains the possibilities for the kind of direct-sum phenomenon you're looking for. A well-known early result of Shannon (tightened by Lupanov) showed that all Boolean functions are computable by circuits of size $O(2^n/n)$, and by Shannon’s counting argument this is tight for random functions. One might think that, at least for moderate values of $m$, the circuit complexity of computing $m$ instances of a random $f$ would scale as $m 2^n/n$. However, Dietmar Uhlig showed in

"Networks computing Boolean functions for multiple input values"

that this is false: as long as $m = 2^{o(n/\log n)}$, one can compute $m$ instances of any $f$ with a circuit of size $O(2^n/n)$--essentially the same cost as for $m = 1$!

I can't find an un-gated copy online, or a homepage for the author, but I came across the paper in this proceedings:

Boolean Function Complexity (London Mathematical Society Lecture Note Series)

Answer 3

Regarding Algebraic complexity, I don't know an example where exponential complexity goes down to sub-exponential amortized complexity, but at least there's a simple example that the complexity of M disjoint copies can be significantly less than M times the complexity of a single copy:

For a "random" n*n matrix A, the complexity of the bilinear form defined by A, (the function f_A(x,y)=xAy, where x and y are 2 vectors of length n) is Omega(n^2) -- this can be shown by a "counting-like" dimension argument since you need n^2 "places" in the circuit to put constants. However, given n different pairs of vectors (x^1,y^1)...(x^n,y^n), you can put the x's into the rows of an n*n matrix X, and similarly the y's into the columns of a matrix Y, and then read all the answers x^iAy^i from the diagonal of XAY, where the this is computed in n^2.3 (or so) operations using fast matrix multiplication, significantly less than n*n^2.

Answer 4

This was studied and solved by Wolfgang Paul who showed essentially what is discussed holds.