A fundamental question of complexity theory is the direct product question. A famous example is Yao's XOR-lemma, [19] in which one assumes that some function f is hard on average for small circuits, (meaning that every circuit of some fixed size 5 which attempts to compute f is wrong on a non-negligible fraction of the inputs) and concludes that every circuit of size s' has a small advantage over guessing randomly when computing f{sup}({direct +}k)(x{sub}1,...,x{sub}k) = f(x{sub}1){direct +}...{direct +}f(x{sub}k) on independently chosen x{sub}1,..., x{sub}k. All known proofs of this lemma, [12, 6, 8, 5] have the feature that s' < s. In words, the circuit which attempts to compute f{sup}({direct +}k) is smaller than the circuit which attempts to compute f on a single input! This paper addresses the issue of proving strong direct product assertions, that is ones in which s' ≈ ks and is in particular larger than s. Since we are unable to "handle" boolean circuits we follow a direction suggested by previous works [13, 15] and study this question in weaker computational models such as decision trees and communication complexity games. 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. Nevertheless, 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 main 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{sup}({direct +}k) is exponentially harder on average for Ω(kc)-bit communication protocols. This follows by showing that disc(f{sup}({direct +}k)) = O(disc(f)){sup}(Ω(k)) which we prove using algebraic techniques inspired by [14]. The main technical step in the proof may be of independent interest and establishes a polynomial relation between the discrepancy of a matrix and its spectral norm. As for weakening the conclusion, we introduce the notion of fair algorithms which restricts the algorithm attempting to compute f{sup}({direct +}k) to spend its computational resource evenly between the k instances. Our third result is an optimal direct product theorem for fair decision trees. It is our hope that the notions suggested in this paper can be extended to stronger computational models.
展开▼
