Are there known to exist functions with the following direct-sum property? 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.
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&lt;=2^N we have xi=i, and for 2^N &lt; i &lt;=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.