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

Itzhak Parnafes; Ran Raz; Avi Wigderson

doi:10.1145/258533.258620

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

Itzhak Parnafes, Ran Raz, Avi Wigderson

Research output: Contribution to journal › Conference article › peer-review

36 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 language	English (US)
Pages (from-to)	363-372
Number of pages	10
Journal	Conference Proceedings of the Annual ACM Symposium on Theory of Computing
DOIs	https://doi.org/10.1145/258533.258620
State	Published - 1997
Externally published	Yes
Event	Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing - El Paso, TX, USA Duration: May 4 1997 → May 6 1997

All Science Journal Classification (ASJC) codes

Software

Access to Document

10.1145/258533.258620

Cite this

@article{411294542c16462fabb0c8d785118d41,

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

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.",

author = "Itzhak Parnafes and Ran Raz and Avi Wigderson",

year = "1997",

doi = "10.1145/258533.258620",

language = "English (US)",

pages = "363--372",

journal = "Conference Proceedings of the Annual ACM Symposium on Theory of Computing",

issn = "0734-9025",

publisher = "Association for Computing Machinery (ACM)",

}

TY - JOUR

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

AU - Parnafes, Itzhak

AU - Raz, Ran

AU - Wigderson, Avi

PY - 1997

Y1 - 1997

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0030671785&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0030671785&partnerID=8YFLogxK

U2 - 10.1145/258533.258620

DO - 10.1145/258533.258620

M3 - Conference article

AN - SCOPUS:0030671785

SN - 0734-9025

SP - 363

EP - 372

JO - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

JF - Conference Proceedings of the Annual ACM Symposium on Theory of Computing

T2 - Proceedings of the 1997 29th Annual ACM Symposium on Theory of Computing

Y2 - 4 May 1997 through 6 May 1997

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this