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.
