Direct product results and the GCD problem, in old and new communication models
Itzhak Parnafes, Ran Raz, Avi Wigderson · 1997
This paper contains several results regarding the communication complexitymodel and the 2-prover games model, which are based on interaction between the two models:1. 2.The We show how to improve the rate of exponential decrease in the parallel repetition theorem of [Ra] in terms of the communication complexity of the verifier's predicate.We apply the improved parallel repetition theorem of 2-prover games to derive, for the first time, a direct product theorem for communication complexity.second derivation uses a common .qeneralization of the two models, which is independently interesting.We initiate a study of its power by considering the GCD problem, and some variations of it, which exhibit a power gap between the new model and the classical communication complexity model.This gap is partly based on the following upper bounds: Given n-bzt inputs x and y to Alice and Bob respectively, they can achieve the tasks below with very high probability using only O(n/ log n) communication bits:1. Decide if GCD(X, y) = 1.