Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Shaltiel, R. Towards proving strong direct product theorems. comput. complex. 12, 1–22 (2003). https://doi.org/10.1007/s00037-003-0175-x
Received:
Issue Date:
DOI: https://doi.org/10.1007/s00037-003-0175-x