• DocumentCode
    1992681
  • 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
  • fYear
    1994
  • fDate
    28 Jun- 1 Jul 1994
  • Firstpage
    88
  • Lastpage
    96
  • 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;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Structure in Complexity Theory Conference, 1994., Proceedings of the Ninth Annual
  • Conference_Location
    Amsterdam
  • Print_ISBN
    0-8186-5670-0
  • Type

    conf

  • DOI
    10.1109/SCT.1994.315814
  • Filename
    315814
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=1992681