Title :
A direct product theorem
Author :
Impagliazzo, Russell ; Raz, Ran ; Wigderson, Avi
Author_Institution :
Dept. of Comput. Sci., California Univ., San Diego, La Jolla, CA, USA
fDate :
28 Jun- 1 Jul 1994
Abstract :
Gives a general setting in which the complexity (or quality) of solving two independent problems is the product of the associated individual complexities. The authors then derive from this setting several concrete results of this type for decision trees and communication complexity
Keywords :
communication complexity; computational complexity; decision theory; trees (mathematics); communication complexity; complexity product; decision trees; direct product theorem; independent problems; solution quality; Complexity theory; Computational modeling; Computer science; Concrete; Decision trees; Distributed computing; Radio access networks;
Conference_Titel :
Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
Conference_Location :
Amsterdam
Print_ISBN :
0-8186-5670-0
DOI :
10.1109/SCT.1994.315814
