Towards proving strong direct product theorems
Ronen Shaltiel · Computational Complexity · 2002
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^{\bigoplus k}(x_{1},...,x_{k}) = f(x_{1})\bigoplus...\bigoplus f(x_{k}) $$ on independently chosen $$ x_{1},...,x_{k} $$ . All known proofs of this lemma have the property that s’ < s . In words, the circuit which attempts to compute $$ f^{\bigoplus 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' \approx ks $$ and is in particular larger than s. We study the question of proving strong direct product question for decision trees and communication protocols.