15
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Clever! One minor thing: we have to sort the triplets stably (or in some other method which guarantees that the triplets with fi≠“” come earlier than the triplets with fi=“”). $\endgroup$ – Tsuyoshi Ito Nov 17 '10 at 19:15
  • $\begingroup$ Very clever, and thanks. Does anything similar work, however, in the algebraic complexity setting, or not? $\endgroup$ – matt hastings Nov 17 '10 at 19:25
  • 1
    $\begingroup$ I guess another way to say this in the case M goes to infinity is that you can invest 2^N*2^N time to build a hash table for all the values of f, and then you can compute every copy in O(N) time. I think there's another reason we at least shouldn't know if something like that is true, even for milder values of N, which is that it would give better than known lower bounds. You'd be able to construct a function with superlinear lower bound by first brute forcing to find a function on n'=log n (or maybe n'=loglog n) inputs with large complexity and then taking n/n'copies of it. $\endgroup$ – Boaz Barak Nov 18 '10 at 6:00
  • 1
    $\begingroup$ In the argument above on why such results lead to lower bounds I don't know if the number of repetitions is really milder, but it does apply to infinite fields as well. $\endgroup$ – Boaz Barak Nov 18 '10 at 6:10
  • $\begingroup$ Hi Boaz, In fact your comment is precisely why I was interested in the existence of these functions. However, there is a subtle point, the "brute forcing". It could be (which is what my question aimed at), that such functions exist but that we have no algorithm that will allow us to demonstrate that a given function has this property. After all, there doesn't seem to be a way to brute force the property that such a lower bound holds for all M, because you'd have to check an infinite number of different circuits. So, perhaps such functions exist for infinite fields but we can't show it. $\endgroup$ – matt hastings Nov 18 '10 at 13:35
10
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ Thanks! Wasn't there a question that asked about paradoxes in TCS? This could also serve as an answer there :) $\endgroup$ – arnab Nov 17 '10 at 19:39
  • $\begingroup$ Thanks for this answer also. Not being able to read the proceedings, I'll guess that similar to the previous answer it may rely on the finite number of possible inputs, so again that same follow-up question as above: what about in the algebraic complexity case? $\endgroup$ – matt hastings Nov 17 '10 at 19:42
  • $\begingroup$ Actually, it appears Shannon first proved the O(2^n/n) upper bound; Lupanov got the right leading constant. I corrected this. The details are explained in "Reviewing bounds on the circuit size of the hardest functions", by Frandsen and Miltersen. $\endgroup$ – Andy Drucker Nov 19 '10 at 15:14
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, I know that example. A similar one is that there exist degree n polynomials in one variable which take time n to evaluate at a given point (though I don't think there are any explicit examples, am I wrong?) However, one can evaluate such a polynomial at n points in time n log^2(n). $\endgroup$ – matt hastings Nov 18 '10 at 13:38
  • 1
    $\begingroup$ I found two papers from the '80s on the algebraic direct-sum problem: "On the validity of the direct sum conjecture" by Ja'ja and Takche, and "On the extended direct sum conjecture" by Bshouty. I can't summarize their contents, but perhaps they'll be helpful. $\endgroup$ – Andy Drucker Nov 19 '10 at 15:22
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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