Direct product results and the GCD problem, in old and new communication models

Itzhak Parnafes, Ran Raz, Avi Wigderson

Research output: Contribution to journalConference articlepeer-review

32 Scopus citations

Abstract

The interaction between the communication complexity model and 2-prover games model showed how to improve the rate of exponential decrease in the parallel repetition theorem in terms of the communication complexity of the verifier's predicate and applies the improved parallel repetition theorem to the 2-prover games to derive a direct product theorem for communication complexity. A common generalization of the two models initiated a study of considering the GCD problem which exhibits a power gap between the new model and the classical communication complexity model. A complete analysis of the communication complexity of these problems is discussed.

Original languageEnglish (US)
Pages (from-to)363-372
Number of pages10
JournalConference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs
StatePublished - 1997
EventProceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA
Duration: May 4 1997May 6 1997

All Science Journal Classification (ASJC) codes

  • Software

Fingerprint Dive into the research topics of 'Direct product results and the GCD problem, in old and new communication models'. Together they form a unique fingerprint.

Cite this