A direct product theorem

摘要

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.