<p>(1): This question was studied in the paper "Towards proving strong direct product theorems" by Ronen Shaltiel, and it turns out that such a conjecture is false: For example, it could be that $f$ can be computed with probability $0.99 * p$ with size much smaller than $s$, and only the additional $0.01 * p$ probability mass requires size $s$. In such case, when computing $f$ on $k$ instances, the circuit could solve $f$ on most of the instances with size much smaller than $s$, and will need size $s$ only on few of the instances.</p>

<p>(2): A direct product theorem for worst-case complexity is known for formulas and for monotone circuits, but is actually known to be false for general circuits. For an easy example, consider a function $f : \{0,1\}^n \to \{0,1\}^n$ that views its input as a vector and multiplies it by some fixed $n \times n$ boolean matrix. Then, computing the function $f$  may require size $n^2$, but computing it on $n$ instances can be done much faster than $n^3$ using a matrix multiplication algorithm.
You can find a thorough discussion of this subject in the book "The complexity of Boolean Functions" by Ingo Wegener - see Chapter 10.2 here: <a href="http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/" rel="nofollow">http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/</a>.</p>

CC BY-SA 3.0
2012-04-22T04:12:01.980Z
I took a look at Chapter 10.2 of Wegener's book (thanks for the reference!) that shows that a direct-sum result cannot hold in general. But is anything known for specific $f$ (perhaps those having circuit complexity smaller than $2^n$)? (I am still interested in worst-case complexity, and for arbitrary circuits.)
user6584
CC BY-SA 3.0
2012-04-22T20:37:54.487Z
I would also be interested if any weaker results are known, e.g., that computing $k$ copies of $f$ requires size $s+O(k)$...
user6584
CC BY-SA 3.0
2012-04-23T05:37:11.757Z
For functions having circuit complexity smaller than $2^n$ - see above the example with matrix multiplication. As for the weaker result you mention - such a result is trivial, since in order to compute $k$ copies of $f$, you need to add at least $k$ output wires to the circuit computing $f$ on one instance.
Or Meir
CC BY-SA 3.0
2012-04-21T08:07:28.773Z
2012-06-06T09:13:51.293Z
2012-06-06T09:13:51.293Z
Or Meir
<p>Just to complement Or's reply, questions of the flavor of (1) [how much of a resource is needed to do well on k copies] were studied, and the corresponding theorems are called "direct sum theorems". As with direct product theorems, direct sum theorems may or may not hold, depending on the setup.</p>

CC BY-SA 3.0
2012-04-21T12:35:41.463Z
2012-04-21T12:35:41.463Z
Dana Moshkovitz
<p>A direct product theorem, informally, says that computing $k$ instances of a function $f$ is harder than computing $f$ once.</p>

<p>Typical direct product theorems (e.g., Yao's XOR Lemma) look at <em>average-case complexity</em>, and argue (very roughly) that is $f$ cannot be computed by circuits of size $s$ with probability better than $p$, then $k$ copies of $f$ cannot be computed by circuits of size $s&#39; &lt; s$ with probability better than $p^k$. </p>

<p>I am looking for different types of direct product theorems (if they are known). Specifically:</p>

<p>(1) Say we fix the probability of error $p$ and are instead interested in te size of the circuit needed to compute $k$ copies of $f$? Is there a result that says that if $f$ cannot be computed by circuits of size $s$ with probability better than $p$, then $k$ copies of $f$ cannot be computed with probability better than $p$ using a circuit of size less than $O(k \cdot s)$?</p>

<p>(2) What is known with respect to <em>worst-case</em> complexity? E.g., if $f$ cannot be computed (with 0 error) by circuits of size $s$, what can we say about the complexity of computing $k$ copies of $f$ (with 0 error)?</p>

<p>Any references would be appreciated.</p>

<cc.complexity-theory><circuit-complexity><average-case-complexity>
Variants of direct product theorems
user6584
# Variants of direct product theorems

(Asked by: username_0 on 2012-04-20)

A direct product theorem, informally, says that computing $k$ instances of a function $f$ is harder than computing $f$ once.

Typical direct product theorems (e.g., Yao's XOR Lemma) look at *average-case complexity*, and argue (very roughly) that is $f$ cannot be computed by circuits of size $s$ with probability better than $p$, then $k$ copies of $f$ cannot be computed by circuits of size $s' < s$ with probability better than $p^k$.

I am looking for different types of direct product theorems (if they are known). Specifically:

(1) Say we fix the probability of error $p$ and are instead interested in te size of the circuit needed to compute $k$ copies of $f$? Is there a result that says that if $f$ cannot be computed by circuits of size $s$ with probability better than $p$, then $k$ copies of $f$ cannot be computed with probability better than $p$ using a circuit of size less than $O(k \cdot s)$?

(2) What is known with respect to *worst-case* complexity? E.g., if $f$ cannot be computed (with 0 error) by circuits of size $s$, what can we say about the complexity of computing $k$ copies of $f$ (with 0 error)?

Any references would be appreciated.

**Tags:** cc.complexity-theory, circuit-complexity, average-case-complexity

---

## 2 answers

### Answer by username_1 on 2012-04-21. Score: 10

(1): This question was studied in the paper "Towards proving strong direct product theorems" by Ronen Shaltiel, and it turns out that such a conjecture is false: For example, it could be that $f$ can be computed with probability $0.99 \* p$ with size much smaller than $s$, and only the additional $0.01 \* p$ probability mass requires size $s$. In such case, when computing $f$ on $k$ instances, the circuit could solve $f$ on most of the instances with size much smaller than $s$, and will need size $s$ only on few of the instances.

(2): A direct product theorem for worst-case complexity is known for formulas and for monotone circuits, but is actually known to be false for general circuits. For an easy example, consider a function $f : \{0,1\}^n \to \{0,1\}^n$ that views its input as a vector and multiplies it by some fixed $n \times n$ boolean matrix. Then, computing the function $f$ may require size $n^2$, but computing it on $n$ instances can be done much faster than $n^3$ using a matrix multiplication algorithm.
You can find a thorough discussion of this subject in the book "The complexity of Boolean Functions" by Ingo Wegener - see Chapter 10.2 here: <http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/>.

> **Comments:**
> **username_0**: I took a look at Chapter 10.2 of Wegener's book (thanks for the reference!) that shows that a direct-sum result cannot hold in general. But is anything known for specific $f$ (perhaps those having circuit complexity smaller than $2^n$)? (I am still interested in worst-case complexity, and for arbitrary circuits.)  
> **username_0**: I would also be interested if any weaker results are known, e.g., that computing $k$ copies of $f$ requires size $s+O(k)$...  
> **username_1**: For functions having circuit complexity smaller than $2^n$ - see above the example with matrix multiplication. As for the weaker result you mention - such a result is trivial, since in order to compute $k$ copies of $f$, you need to add at least $k$ output wires to the circuit computing $f$ on one instance.  

---

### Answer by username_2 on 2012-04-21. Score: 7

Just to complement Or's reply, questions of the flavor of (1) [how much of a resource is needed to do well on k copies] were studied, and the corresponding theorems are called "direct sum theorems". As with direct product theorems, direct sum theorems may or may not hold, depending on the setup.


---

