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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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/.

Improve this answer
$\endgroup$
3
  • $\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$
    – user6584
    Apr 22, 2012 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$
    – user6584
    Apr 22, 2012 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, 2012 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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