Title: Towards proving strong direct product theorems
Abstract: A fundamental question of complexity theory is the direct product question. A famous example is Yao's (1982) 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' has a small advantage over guessing randomly when computing f/sup /spl oplus/k/ (x/sub 1/, ..., x/sub k/)=f(x/sub 1/)/spl oplus/.../spl oplus/f(x/sub k/) on independently chosen x/sub 1/, ..., x/sub k/. All known proofs of this lemma have the feature that s'<s. In words, the circuit which attempts to compute f/sup /spl oplus/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'/spl ap/ks and is in particular larger than s. Since we are unable to "handle" boolean circuits we follow a direction suggested by previous works (Nisan et al., 1994; Parnafes et al., 1997) and study this question in weaker computational models such as decision trees and communication complexity games.
Publication Year: 2002
Publication Date: 2002-11-13
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 28
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot