Direct product theorem

Russell Impagliazzo, Ran Raz, Avi Wigderson

Research output: Chapter in Book/Report/Conference proceedingConference contribution

11 Scopus citations

Abstract

We give a general setting in which the complexity (or quality) of solving two independent problems is the product of the associated individual complexities. We then derive from it several concrete results of this type for decision trees and communication complexity.

Original languageEnglish (US)
Title of host publicationProceedings of the IEEE Annual Structure in Complexity Theory Conference
Editors Anon
PublisherPubl by IEEE
Pages88-96
Number of pages9
ISBN (Print)0818656727
StatePublished - Dec 1 1994
Externally publishedYes
EventProceedings of the 9th Annual Structure in Complexity Theory Conference - Amsterdam, Neth
Duration: Jun 28 1994Jul 1 1994

Publication series

NameProceedings of the IEEE Annual Structure in Complexity Theory Conference
ISSN (Print)1063-6870

Other

OtherProceedings of the 9th Annual Structure in Complexity Theory Conference
CityAmsterdam, Neth
Period6/28/947/1/94

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Direct product theorem'. Together they form a unique fingerprint.

Cite this