{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,6]],"date-time":"2026-10-06T14:12:43Z","timestamp":1791295963212,"version":"4.1.0"},"reference-count":45,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:p>We show that a parallel repetition of any two-prover one-round proof system (MIP(2,1)) decreases the probability of error at an exponential rate. No constructive bound was previously known. The constant in the exponent (in our analysis) depends only on the original probability of error and on the total number of possible answers of the two provers. The dependency on the total number of possible answers is logarithmic, which was recently proved to be almost the best possible [U. Feige and O. Verbitsky, Proc.11th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, Los Alamitos, CA, 1996, pp. 70--76].<\/jats:p>","DOI":"10.1137\/s0097539795280895","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"763-803","source":"Crossref","is-referenced-by-count":443,"title":["A Parallel Repetition Theorem"],"prefix":"10.1137","volume":"27","author":[{"given":"Ran","family":"Raz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,28]]},"reference":[{"key":"R1","unstructured":"N. Alon,\n                      Probabilistic methods in extremal finite set theory\n                      , in Proc. Conference on Extremal Problems for Finite Sets, Bolyai Soc. Math. Stud. 3, J\u00e1anos Bolyai Society, Budapest, Hungary, 1994, pp. 39\u201357."},{"key":"R2","unstructured":"S. Arora,\n                      Proof Verification and Hardness of Approximation Problems\n                      , Ph.D. dissertation, University of California, Berkeley, CA, http:\/\/www.cs.princeton.edu\/\u223carora, 1994."},{"key":"R3","unstructured":"S. Arora and C. Lund,\n                      Hardness of approximations\n                      , in Approximation Algorithms for NPHard Problems, D. Hochbaum, ed., PWS Publishing, Boston, MA, 1996; also available online from http:\/\/www.cs.princeton.edu\/\u223carora."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"S. Arora and S. Safra,\n                      Probabilistic checking of proofs: A new characterization of NP\n                      , in Proc. FOCS 1992, IEEE Computer Society Press, Los Alamitos, CA, pp. 2\u201313.","DOI":"10.1109\/SFCS.1992.267824"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy,\n                      Proof verification and intractability of approximation problems\n                      , in Proc. FOCS 1992, IEEE Computer Society Press, Los Alamitos, CA, pp. 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"R6","unstructured":"M. Bellare,\n                      Interactive proofs and approximation\n                      , in Proc. Israel Symposium on Theory of Computing and Systems, IEEE Computer Society Press, Los Alamitos, CA, 1993, pp. 266\u2013274."},{"key":"R7","doi-asserted-by":"crossref","unstructured":"L. Babai, L. Fortnow, and C. Lund,\n                      Non\u2010deterministic exponential time has two\u2010prover interactive protocols\n                      , in Proc. FOCS 1990, IEEE Computer Society Press, Los Alamitos, CA, pp. 16\u201325.","DOI":"10.1109\/FSCS.1990.89520"},{"key":"R8","doi-asserted-by":"crossref","unstructured":"M. Bellare, S. Goldwasser, C. Lund, and A. Russell,\n                      Efficient probabilistic checkable proofs and applications to approximation\n                      , in Proc. STOC 1993, ACM, New York, pp. 294\u2013304.","DOI":"10.1145\/167088.167174"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302531"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/BF01585569"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"M. Bellare and M. Sudan,\n                      Improved non\u2010approximability results\n                      , in Proc. STOC 1994, ACM, New York, pp. 184\u2013193.","DOI":"10.1145\/195058.195129"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"M. Ben\u2010or, S. Goldwasser, J. Kilian, and A. Wigderson,\n                      Multi prover interactive proofs: How to remove intractability\n                      , in Proc. STOC 1988, ACM, New York, pp. 113\u2013131.","DOI":"10.1145\/62212.62223"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"M. Ben\u2010or, S. Goldwasser, J. Kilian, and A. Wigderson,\n                      Efficient identification schemes using two prover interactive proofs\n                      , in Proc. Crypto 1989, Springer\u2010Verlag, New York, 1990, pp. 498\u2013506.","DOI":"10.1007\/0-387-34805-0_44"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"J. Cai, A. Condon, and R. Lipton,\n                      On bounded round multi\u2010prover interactive proof systems\n                      , in Proc. Structure in Complexity Theory, 1990, IEEE Computer Society Press, Los Alamitos, CA, pp. 45\u201354.","DOI":"10.1109\/SCT.1990.113953"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90085-T"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80026-1"},{"key":"R17","unstructured":"I. Csiszar and J. Korner,\n                      Information Theory: Coding Theorems for Discrete Memoryless Systems\n                      , Academic Press, New York, London, 1981."},{"key":"R18","unstructured":"C. Dwork, U. Feige, J. Kilian, M. Naor, and S. Safra,\n                      Low communication, 2\u2010prover zero\u2010knowledge proofs for NP\n                      , in Proc. Crypto 1992, Springer\u2010Verlag, Berlin, pp. 217\u2013229."},{"key":"R19","doi-asserted-by":"crossref","unstructured":"U. Feige,\n                      On the success probability of the two provers in one round proof systems\n                      , in Proc. Structures 1991, pp. 116\u2013123.","DOI":"10.1109\/SCT.1991.160251"},{"key":"R20","unstructured":"U. Feige,\n                      Error Reduction by Parallel Repetition: The State of the Art\n                      , Technical report CS95\u201032, Weizmann Institute of Science, Rehovot, Israel."},{"key":"R21","unstructured":"L. Fortnow,\n                      Complexity\u2010Theoretic Aspects of Interactive Proof Systems\n                      , Ph.D. thesis, Report MIT\/LCS\/TR\u2010447, MIT, Cambridge, MA, 1989."},{"key":"R22","doi-asserted-by":"crossref","unstructured":"U. Feige, S. Goldwasser, L. Lovasz, M. Safra, and M. Szegedy,\n                      Approximating clique is almost NP\u2010complete\n                      , in Proc. FOCS 1991, IEEE Computer Society Press, Los Alamitos, CA, pp. 2\u201312.","DOI":"10.1109\/SFCS.1991.185341"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"U. Feige and J. Kilian,\n                      Two prover protocols: Low error at affordable rates\n                      , in Proc. STOC 1994, ACM, New York, pp. 172\u2013183.","DOI":"10.1145\/195058.195128"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"U. Feige and J. Kilian,\n                      Impossibility results for recycling random bits in two prover proof systems\n                      , in Proc. STOC 1995, ACM, New York, pp. 457\u2013468.","DOI":"10.1145\/225058.225183"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"U. Feige and L. Lovasz,\n                      Two\u2010prover one\u2010round proof systems, their power and their problems\n                      , in Proc. STOC 1992, ACM, New York, pp. 733\u2013744.","DOI":"10.1145\/129712.129783"},{"key":"R26","doi-asserted-by":"crossref","unstructured":"L. Fortnow, J. Rompel, and M. Sipser,\n                      On the power of multi\u2010prover interactive protocols\n                      , in Proc. Structures 1988, pp. 156\u2013161.","DOI":"10.1109\/SCT.1988.5275"},{"key":"R27","doi-asserted-by":"crossref","unstructured":"U. Feige and O. Verbitsky,\n                      Error reduction by parallel repetition: A negative result\n                      , in Proc. 11th Annual IEEE Conference on Computational Complexity, 1996, IEEE Computer Society Press, Los Alamitos, CA, pp. 70\u201376.","DOI":"10.1109\/CCC.1996.507669"},{"key":"R28","unstructured":"L. Fortnow, J. Rompel, and M. Sipser,\n                      Errata for \u201cOn the power of multi\u2010prover interactive protocols\n                      ,\u201d in Proc. Structure in Complexity Theory 1990, IEEE Computer Society Press, Los Alamitos, CA, pp. 318\u2013319."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"R. M. Gray,\n                      Entropy and Information Theory\n                      , Springer\u2010Verlag, New York, 1990.","DOI":"10.1007\/978-1-4757-3982-4"},{"key":"R30","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad,\n                      Testing of the long code and hardness for clique\n                      , in Proc. STOC 1996, ACM, New York, pp. 11\u201319.","DOI":"10.1145\/237814.237820"},{"key":"R31","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad,\n                      Clique is Hard to Approximate Within n1-\u03b5,\n                      in Proc. FOCS 1996, IEEE Computer Society Press, Los Alamitos, CA, pp. 627\u2013636.","DOI":"10.1109\/SFCS.1996.548522"},{"key":"R32","doi-asserted-by":"crossref","unstructured":"J. H\u00e5stad,\n                      Some optimal inapproximability results\n                      , in Proc. STOC 1997, ACM, New York, pp. 1\u201310.","DOI":"10.1145\/258533.258536"},{"key":"R33","unstructured":"J. Kilian,\n                      Strong Separation Models of Multi Prover Interactive Proofs\n                      , DIMACS Workshop on Cryptography, October 1990."},{"key":"R34","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz and N. Nisan,\n                      Communication Complexity\n                      , Cambridge University Press, London, Cambridge, 1997.","DOI":"10.1017\/CBO9780511574948"},{"key":"R35","doi-asserted-by":"crossref","unstructured":"B. Kalyanasundaram and G. Schnitger,\n                      The probabilistic communication complexity of set intersection\n                      , in Proc. Structure in Complexity Theory 1987, IEEE Computer Society Press, Los Alamitos, CA, pp. 41\u201349.","DOI":"10.1109\/PSCT.1987.10319253"},{"key":"R36","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200756"},{"key":"R37","doi-asserted-by":"crossref","unstructured":"D. Lapidot and A. Shamir,\n                      Fully parallelized multi prover protocols for NEXP\u2010time\n                      , in Proc. FOCS 1991, IEEE Computer Society Press, Los Alamitos, CA, pp. 13\u201318.","DOI":"10.1109\/SFCS.1991.185342"},{"key":"R38","doi-asserted-by":"crossref","unstructured":"C. Lund and M. Yannakakis,\n                      On the hardness of approximating minimization problems\n                      , in Proc. STOC 1993, ACM, New York, pp. 286\u2013293.","DOI":"10.1145\/167088.167172"},{"key":"R39","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)E0185-7"},{"key":"R40","doi-asserted-by":"crossref","unstructured":"R. Raz,\n                      A parallel repetition theorem\n                      , in Proc. STOC 1995, ACM, New York, pp. 447\u2013556.","DOI":"10.1145\/225058.225181"},{"key":"R41","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"R42","doi-asserted-by":"crossref","unstructured":"I. Parnafes, R. Raz, and A. Wigderson,\n                      Direct product results and the GCD problem in old and new communication models\n                      , in Proc. STOC 1997, ACM, New York, pp. 363\u2013372.","DOI":"10.1145\/258533.258620"},{"key":"R43","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0066"},{"key":"R44","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00165-4"},{"key":"R45","unstructured":"O. Verbitsky,\n                      The Parallel Repetition Conjecture for Trees is True\n                      , manuscript, 1994."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539795280895","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:40Z","timestamp":1787336020000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539795280895"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1137\/S0097539795280895"],"URL":"https:\/\/doi.org\/10.1137\/s0097539795280895","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}