# Variants of direct product theorems

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.

(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/.
• 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.) Apr 22 '12 at 4:12
• I would also be interested if any weaker results are known, e.g., that computing $k$ copies of $f$ requires size $s+O(k)$... Apr 22 '12 at 20:37
• 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. Apr 23 '12 at 5:37