Parallel repetition: simplifications and the no-signaling case

ABSTRACT

Consider a game where a refereed chooses (x,y) according to a publiclyknown distribution P_XY, sends x to Alice, and y to Bob. Withoutcommunicating with each other, Alice responds with a value "a" and Bobresponds with a value "b". Alice and Bob jointly win if a publiclyknown predicate Q(x,y,a,b) holds. Let such a game be given and assume that the maximum probabilitythat Alice and Bob can win is v<1. Raz (SIAM J. Comput. 27, 1998)shows that if the game is repeated n times in parallel, then the probability that Alice and Bob win all games simultaneously is at most v'^(n/log(s)), where s is the maximal number of possible responses from Alice and Bob in the initial game, and v' is a constant depending only on v. In this work, we simplify Raz's proof in various ways and thus shorten it significantly. Further we study the case where Alice and Bob are not restricted to local computations and can use any strategy which does not imply communication among them.

REFERENCES

• 1: P. Beame. Personal communication, 2006.
• 2: Michael Ben-Or , Shafi Goldwasser , Joe Kilian , Avi Widgerson, Multi-prover interactive proofs: how to remove intractability assumptions, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.113-131, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62223]
• 3: G. Brassard, A. Broadbent, and A. Tapp. Quantum pseudo-telepathy. Foundations of Physics, 35(11):1877--1907, 2005. (quant-ph/0407221).
• 4: Jin-yi Cai , Anne Condon , Richard J. Lipton, On games of incomplete information, Theoretical Computer Science, v.103 n.1, p.25-38, 24 Aug. 1992 [doi>10.1016/0304-3975(92)90085-T]
• 5: B.S. Cirel'son. Quantum generalizations of Bell's inequality. Letters in Mathematical Physics, 4(2):93--100, 1980.
• 6: J.F. Clauser, M.A. Horne, A. Shimony, and R.A. Holt. Proposed experiment to test local hidden-variable theories. Physical Review Letters, 23(15):880--884, 1969.
• 7: R. Cleve, W. Slofstra, F. Unger, and S. Upadhyay. Strong parallel repetition theorem for quantum XOR proof systems, 2006. (quant-ph/0608146).
• 8: Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
• 9: U. Feige. On the success probability of the two provers in one-round proof systems. In Proceedings of the sixth Annual Structure in Complexity Theory Conference, pages 116--123, 1991.
• 10: Uriel Feige , László Lovász, Two-prover one-round proof systems: their power and their problems (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.733-744, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129783]
• 11: Uriel Feige , Oleg Verbitsky, Error Reduction by Parallel Repetition—A Negative Result, Combinatorica, v.22 n.4, p.461-478, October 2002 [doi>10.1007/s00493-002-0001-0]
• 12: L. Fortnow. Complexity-Theoretic Aspects of Interactive Proof Systems. PhD thesis, Massachusetts Institute of Technology, 1989.
• 13: Lance Fortnow , John Rompel , Michael Sipser, On the power of multi-prover interactive protocols, Theoretical Computer Science, v.134 n.2, p.545-557, Nov. 21, 1994 [doi>10.1016/0304-3975(94)90251-8]
• 14: T. Holenstein and R. Renner. On the randomness of independent experiments, 2006. (cs.IT/0608007).
• 15: D. Lapidot and A. Shamir. A one-round, two-prover, zero-knowledge protocol for NP. Combinatorica, 15(2):204--214, 1995.
• 16: M.A. Nielsen and I.L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, first edition, 2000. ISBN 0-521-63503-9.
• 17: Itzhak Parnafes , Ran Raz , Avi Wigderson, Direct product results and the GCD problem, in old and new communication models, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.363-372, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258620]
• 18: S. Popescu and D. Rohrlich. Nonlocality as an axiom for quantum theory. Foundations of Physics, 24(3):379--385, March 1994. (quant-ph/9508009).
• 19: Ran Raz, A Parallel Repetition Theorem, SIAM Journal on Computing, v.27 n.3, p.763-803, June 1998 [doi>10.1137/S0097539795280895]
• 20: O. Verbitsky. Towards the parallel repetition conjecture. In Structure in Complexity Theory Conference, pages 304--307, 1994.
• 21: J. Watrous. A note on parallel repetition of two-prover quantum-interactive proofs, 2002. Manuscript.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Proof theory

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

General Terms:
Theory

Keywords:
parallel repetition, probabilistically checkable proofs