Towards proving strong direct product theorems

A fundamental question of complexity theory is the direct product question. A famous example is Yao’s XOR-lemma, in which one assumes that some function f is hard on average for small circuits (meaning that every circuit of some fixed size s which attempts to compute f is wrong on a non-negligible fraction of the inputs) and concludes that every circuit of size s’ only has a small advantage over guessing randomly when computing fᵏ(x₁,...,xₖ) = f(x₁)... f(xₖ) on independently chosen x₁,...,xₖ . All known proofs of this lemma have the property that s’ < s . In words, the circuit which attempts to compute fᵏ 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. We study the question of proving strong direct product question for decision trees and communication protocols.