Parallel Repetition: Simplification and the No-Signaling Case

by Thomas Holenstein

Theory of Computing, Volume 5(8), pp. 141-172, 2009

Bibliography with links to cited articles

[1]   Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy: Proof verification and hardness of approximation problems. In Proc. 33rd FOCS, pp. 14–23. IEEE Comp. Soc. Press, 1992. [doi:10.1109/SFCS.1992.267823].

[2]   Sanjeev Arora and Shmuel Safra: Probabilistic checking of proofs; a new characterization of NP. In Proc. 33rd FOCS, pp. 2–13. IEEE Comp. Soc. Press, 1992. [doi:10.1109/SFCS.1992.267824].

[3]   Boaz Barak, Moritz Hardt, Ishay Haviv, Anup Rao, Oded Regev, and David Steurer: Rounding parallel repetition of unique games. In Proc. 49th FOCS, pp. 374–383. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.31].

[4]   Paul Beame: Personal communication, 2006.

[5]   Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Wigderson: Multi-prover interactive proofs: How to remove intractability assumptions. In Proc. 20th STOC, pp. 113–132. ACM Press, 1988. [doi:10.1145/62212.62223].

[6]   Gilles Brassard, Anne Broadbent, and Alain Tapp: Quantum pseudo-telepathy. Foundations of Physics, 35(11):1877–1907, 2005. [doi:10.1007/s10701-005-7353-4, arXiv:quant-ph/0407221].

[7]   Andrei Z. Broder, Steven C. Glassman, Mark S. Manasse, and Geoffrey Zweig: Syntactic clustering of the web. Computer Networks, 29(8–13):1157–1166, 1997.

[8]   Jin-yi Cai, Anne Condon, and Richard J. Lipton: On games of incomplete information. Theoretical Computer Science, 103(1):25–38, 1992. [doi:10.1016/0304-3975(92)90085-T].

[9]   Boris S. Cirel’son: Quantum generalizations of Bell’s inequality. Lett. Math. Phys., 4(2):93–100, 1980. [doi:10.1007/BF00417500].

[10]   John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett., 23(15):880–884, 1969. [doi:10.1103/PhysRevLett.24.549].

[11]   Richard Cleve, William Slofstra, Falk Unger, and Sarvagya Upadhyay: Perfect parallel repetition theorem for quantum XOR proof systems. Computational Complexity, 17(2):282–299, 2008. [doi:10.1007/s00037-008-0250-4].

[12]   Thomas M. Cover and Joy A. Thomas: Elements of Information Theory. John Wiley & Sons, Inc., second edition, 1991. ISBN 0-471-24195-4.

[13]   Uriel Feige: On the success probability of the two provers in one-round proof systems. In Proc. 6th Ann. Structure in Complexity Theory Conf., pp. 116–123. IEEE Comp. Soc. Press, 1991. [doi:10.1109/SCT.1991.160251].

[14]   Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, and Mario Szegedy: Approximating clique is almost NP-complete (preliminary version). In Proc. 32nd FOCS, pp. 2–12. IEEE Comp. Soc. Press, 1991. [doi:10.1109/SFCS.1991.185341].

[15]   Uriel Feige, Guy Kindler, and Ryan O’Donnell: Understanding parallel repetition requires understanding foams. In Proc. IEEE Conf. Comput. Complexity, pp. 179–192. IEEE Comp. Soc. Press, 2007. [doi:10.1109/CCC.2007.39].

[16]   Uriel Feige and László Lovász: Two-prover one-round proof systems: Their power and their problems. In Proc. 24th STOC, pp. 733–744. ACM Press, 1992. [doi:10.1145/129712.129783].

[17]   Uriel Feige and Oleg Verbitsky: Error reduction by parallel repetition – a negative result. Combinatorica, 22(4):461–478, 2002. [doi:10.1007/s00493-002-0001-0].

[18]   Lance Fortnow: Complexity-Theoretic Aspects of Interactive Proof Systems. PhD thesis, Massachusetts Institute of Technology, 1989.

[19]   Lance Fortnow, John Rompel, and Michael Sipser: On the power of multi-prover interactive proof systems. Theoretical Computer Science, 134(2):545–557, 1994. [doi:10.1016/0304-3975(94)90251-8].

[20]   Sreenivas Gollapudi and Rina Panigrahy: A dictionary for approximate string search and longest prefix search. In Proc. of 15th ACM Intern. Conf. on Inf. and Knowl. Manag. (CIKM), pp. 768–775. ACM Press, 2006. [doi:10.1145/1183614.1183723].

[21]   Thomas Holenstein: Parallel repetition: Simplifications and the no-signaling case. In Proc. 39th STOC, pp. 411–419. ACM Press, 2007. [doi:10.1145/1250790.1250852].

[22]   Thomas Holenstein and Renato Renner: On the randomness of independent experiments, 2006. [arXiv:cs.IT/0608007].

[23]   Subhash Khot: On the power of unique 2-prover 1-round games. In Proc. 34th STOC, pp. 767–775. ACM Press, 2002. [doi:10.1145/509907.510017].

[24]   Jon M. Kleinberg and Éva Tardos: Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields. J. ACM, 49(5):616–639, 2002. [doi:10.1145/585265.585268].

[25]   Dror Lapidot and Adi Shamir: A one-round, two-prover, zero-knowledge protocol for NP. Combinatorica, 15(2):203–214, 1995. [doi:10.1007/BF01200756].

[26]   Mark Manasse, Frank McSherry, and Kunal Talwar: Consistent weighted sampling. Manuscript, 2007.

[27]   Udi Manber: Finding similar files in a large file system. In USENIX Winter, pp. 1–10, 1994.

[28]   Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000. ISBN 0-521-63503-9.

[29]   Itzhak Parnafes, Ran Raz, and Avi Wigderson: Direct product results and the GCD problem, in old and new communication models. In Proc. 29th STOC, pp. 363–372. ACM Press, 1997. [doi:10.1145/258533.258620].

[30]   Sandu Popescu and Daniel Rohrlich: Nonlocality as an axiom for quantum theory. Foundations of Physics, 24(3):379–385, March 1994. [doi:10.1007/BF02058098, arXiv:quant-ph/9508009].

[31]   Anup Rao: Parallel repetition in projection games and a concentration bound. In Proc. 40th STOC, pp. 1–10. ACM Press, 2008. [doi:10.1145/1374376.1374378].

[32]   Ran Raz: A parallel repetition theorem. SIAM J. Comput., 27(3):763–803, 1998. [doi:10.1137/S0097539795280895].

[33]   Ran Raz: A counterexample to strong parallel repetition. In Proc. 49th FOCS, pp. 369–373. IEEE Comp. Soc. Press, 2008. [doi:10.1109/FOCS.2008.49].

[34]   Oleg Verbitsky: Towards the parallel repetition conjecture. In Proc. 9th Ann. Structure in Complexity Theory Conf., pp. 304–307. IEEE Comp. Soc. Press, 1994. [doi:10.1109/SCT.1994.315794].

[35]   John Watrous: A note on parallel repetition of two-prover quantum-interactive proofs, 2002. Manuscript.