A fundamental question of complexity theory is the direct product

question. Namely weather the assumption that a function $f$ is hard on

average for some computational class (meaning that every algorithm from

the class has small advantage over random guessing when computing $f$)

entails that computing $f$ on $k$ independently chosen inputs is

exponentially harder on average.

A famous example is Yao's XOR-lemma, which gives such a result for

boolean circuits. This question has also been studied in other

computational models, such as decision trees, and communication

complexity.

In Yao's XOR-lemma one assumes $f$ is hard on average for circuits of

size $s$ and concludes that

$f^{xor k}(x_1,..,x_k)=f(x_1) xor .. xor f(x_k)$

is essentially exponentially harder on average

for circuits of size $s'$.

All known proofs of this lemma have the feature that $s' < s$. In words,

the circuit which attempts to compute $f^{xor k}$ is {\em smaller} than

the circuit which attempts to compute $f$ on a single input!

This paper addresses the issue of proving {\em strong} direct product

assertions, that is ones in which $s' \approx ks$ and is in particular

{\em larger} than $s$.

Our first result is a counterexample which shows that strong direct

product assertions are simply not true. This holds for every

``reasonable'' model of computation.

While this counterexample rules out the possibility of proving strong

direct product assertions, it seems to exploit defects in the

formulation of the problem rather than show that our general intuition

for strong direct product assertions is false.

Still, in order to prove theorems with a strong direct product flavor

we must change the formulation of the question and either strengthen

the assumption or weaken the conclusion.

An example of strengthening the assumption is given in our second result

in which we prove that if a function $f$ is proved to be hard on average

for $c$-bit communication protocols via the ``discrepancy method'' then

$f^{xor k}$ is exponentially harder on average for $\Omega(kc)$-bit

communication protocols. This follows by showing that

$disc(f^{xor k})=disc(f)^{\Omega(k)}$ which we prove using algebraic

techniques inspired by a paper of Nisan and Wigderson.

As for weakening the conclusion, we introduce the notion of {\em fair}

algorithms which restricts the algorithm attempting to compute

$f^{xor k}$ to spend its computational resource evenly between the $k$

instances.

Our third result is an optimal direct product theorem for fair decision trees.

We show that if $f$ is hard on average for depth $d$ decision trees

then $f^{xor k}$ is exponentially harder for fair decision trees

of depth $kd$.

It is our hope that these notions could be extended to stronger

computational models.