<p>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</p>

<p>"Networks computing Boolean functions for multiple input values"</p>

<p>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$!</p>

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

<p><a href="http://rads.stackoverflow.com/amzn/click/0521408261" rel="nofollow">Boolean Function Complexity (London Mathematical Society Lecture Note Series)</a></p>

CC BY-SA 2.5
2010-11-17T19:39:14.273Z
Thanks!  Wasn't there a question that asked about paradoxes in TCS?  This could also serve as an answer there :)
arnab
CC BY-SA 2.5
2010-11-17T19:42:30.430Z
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?
matt hastings
CC BY-SA 2.5
2010-11-19T15:14:34.103Z
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.
Andy Drucker
CC BY-SA 2.5
2010-11-17T19:36:10.570Z
2010-11-19T15:12:14.857Z
2010-11-19T15:12:14.857Z
Andy Drucker
<p>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:</p>

<p>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.  </p>

CC BY-SA 2.5
2010-11-18T13:38:49.993Z
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).
matt hastings
CC BY-SA 2.5
2010-11-19T15:22:19.870Z
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.
Andy Drucker
CC BY-SA 2.5
2010-11-18T04:29:29.360Z
2010-11-18T04:29:29.360Z
Noam
<p>This was studied and solved by Wolfgang Paul who showed essentially what is discussed holds.</p>

CC BY-SA 3.0
2011-04-23T16:29:21.573Z
Nice! Is there any reference?
Hsien-Chih Chang 張顯之
CC BY-SA 3.0
2011-04-23T14:00:15.960Z
2011-04-23T14:00:15.960Z
dick lipton
<p>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: </p>

<p>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. </p>

CC BY-SA 2.5
2010-11-17T19:15:31.873Z
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=“*”).
Tsuyoshi Ito
CC BY-SA 2.5
2010-11-17T19:25:34.430Z
Very clever, and thanks.  Does anything similar work, however, in the algebraic complexity setting, or not?
matt hastings
CC BY-SA 2.5
2010-11-18T06:00:56.497Z
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.
Boaz Barak
CC BY-SA 2.5
2010-11-18T06:10:51.193Z
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.
Boaz Barak
CC BY-SA 2.5
2010-11-18T13:35:26.830Z
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.
matt hastings
CC BY-SA 2.5
2010-11-19T21:15:35.390Z
@matt it's a good question, I wonder if you have sufficiently large finite time, can you certify that a certain polynomial requires large circuits. (Obviosuly the circuit has to be at least as large as the degree of the polynomial, but maybe there is also a way to certify that circuits with coefficients no larger than some exponential or doubly exponential bound cannot help.)
Boaz Barak
CC BY-SA 3.0
2012-04-22T22:43:17.297Z
For reference: essentially the same result/technique described by Nisan are given in "ON SIMULTANEOUS REALIZATIONS OF
BOOLEAN FUNCTIONS, WITH APPLICATIONS", by Andreas Albrecht, LNCS Vol. 342 (1989).
Andy Drucker
CC BY-SA 3.0
2012-04-23T00:15:34.530Z
Actually, the technique and a quite similar result go back further, to Wolfgang Paul, "Realizing Boolean Functions on Disjoint sets of Variables" Theor. Comput. Sci. Vol 2, number 3, 1976 (as mentioned by Dick Lipton below).
Andy Drucker
CC BY-SA 2.5
2010-11-17T19:06:33.403Z
2010-11-17T19:06:33.403Z
Noam
<p>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.</p>

<p>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.</p>

<cc.complexity-theory><circuit-complexity><algebraic-complexity>
Are there known to exist functions with the following direct-sum property?
matt hastings
# Are there known to exist functions with the following direct-sum property?

(Asked by: username_0 on 2010-11-17)

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.

**Tags:** cc.complexity-theory, circuit-complexity, algebraic-complexity

---

## 4 answers

### Answer by username_3 on 2010-11-17. Score: 13 | Accepted answer

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.

> **Comments:**
> **username_6**: 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=“*”).  
> **username_0**: Very clever, and thanks.  Does anything similar work, however, in the algebraic complexity setting, or not?  
> **username_7**: 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.  
> **username_7**: 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.  
> **username_0**: 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.  
> **username_7**: @matt it's a good question, I wonder if you have sufficiently large finite time, can you certify that a certain polynomial requires large circuits. (Obviosuly the circuit has to be at least as large as the degree of the polynomial, but maybe there is also a way to certify that circuits with coefficients no larger than some exponential or doubly exponential bound cannot help.)  
> **username_1**: For reference: essentially the same result/technique described by Nisan are given in "ON SIMULTANEOUS REALIZATIONS OF BOOLEAN FUNCTIONS, WITH APPLICATIONS", by Andreas Albrecht, LNCS Vol. 342 (1989).  
> **username_1**: Actually, the technique and a quite similar result go back further, to Wolfgang Paul, "Realizing Boolean Functions on Disjoint sets of Variables" Theor. Comput. Sci. Vol 2, number 3, 1976 (as mentioned by Dick Lipton below).  

---

### Answer by username_1 on 2010-11-17. Score: 11

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)](http://rads.stackoverflow.com/amzn/click/0521408261)

> **Comments:**
> **username_2**: Thanks!  Wasn't there a question that asked about paradoxes in TCS?  This could also serve as an answer there :)  
> **username_0**: 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?  
> **username_1**: 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.  

---

### Answer by username_3 on 2010-11-18. Score: 6

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.

> **Comments:**
> **username_0**: 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).  
> **username_1**: 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.  

---

### Answer by username_4 on 2011-04-23. Score: 5

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

> **Comments:**
> **username_5**: Nice! Is there any reference?  

---

