Parallel Repetition: Simplification and the No-Signaling Case
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.