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)|
|Number of pages||10|
|Journal||Conference Proceedings of the Annual ACM Symposium on Theory of Computing|
|State||Published - 1997|
|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