11
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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

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

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.

$\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.