Towards proving strong direct product theorems

摘要

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 k s 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 ( kc ) -bit communication protocols. This follows by showing that disc ( f xor k ) = d isc ( f ) ( 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.