A direct product theorem
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
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
This publication has 17 references indexed in Scilit:
- Fractional covers and communication complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Bounded queries in recursion theory: a surveyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Super-logarithmic depth lower bounds via direct sum in communication complexityPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Fully parallelized multi prover protocols for NEXP-timePublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Rounds in Communication Complexity RevisitedSIAM Journal on Computing, 1993
- Monotone Circuits for Connectivity Require Super-Logarithmic DepthSIAM Journal on Discrete Mathematics, 1990
- On the extended direct sum conjecturePublished by Association for Computing Machinery (ACM) ,1989
- Lower bounds for constant depth circuits in the presence of help bitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- On the Validity of the Direct Sum ConjectureSIAM Journal on Computing, 1986
- On the ratio of optimal integral and fractional coversDiscrete Mathematics, 1975