{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,23]],"date-time":"2026-04-23T01:50:05Z","timestamp":1776909005420,"version":"3.51.2"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"11","license":[{"start":{"date-parts":[[2021,10,25]],"date-time":"2021-10-25T00:00:00Z","timestamp":1635120000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:p>\n            <jats:bold>\n              Note from the Research Highlights Co-Chairs: A Research Highlights paper appearing in\n              <jats:italic>Communications<\/jats:italic>\n              is usually peer-reviewed prior to publication. The following paper is unusual in that it is still under review. However, the result has generated enormous excitement in the research community, and came strongly nominated by SIGACT, a nomination seconded by external reviewers.\n            <\/jats:bold>\n          <\/jats:p>\n          <jats:p>\n            The complexity class NP characterizes the collection of computational problems that have\n            <jats:italic>efficiently verifiable solutions.<\/jats:italic>\n            With the goal of classifying computational problems that seem to lie beyond NP, starting in the 1980s complexity theorists have considered extensions of the notion of efficient verification that allow for the use of\n            <jats:italic>randomness<\/jats:italic>\n            (the class MA),\n            <jats:italic>interaction<\/jats:italic>\n            (the class IP), and the possibility to interact with\n            <jats:italic>multiple<\/jats:italic>\n            proofs, or\n            <jats:italic>provers<\/jats:italic>\n            (the class MIP). The study of these extensions led to the celebrated PCP theorem and its applications to hardness of approximation and the design of cryptographic protocols.\n          <\/jats:p>\n          <jats:p>\n            In this work, we study a fourth modification to the notion of efficient verification that originates in the study of\n            <jats:italic>quantum entanglement.<\/jats:italic>\n            We prove the surprising result that every problem that is recursively enumerable, including the Halting problem, can be efficiently verified by a classical probabilistic polynomial-time verifier interacting with two all-powerful but noncommunicating provers sharing entanglement. The result resolves long-standing open problems in the foundations of quantum mechanics (Tsirelson's problem) and operator algebras (Connes' embedding problem).\n          <\/jats:p>","DOI":"10.1145\/3485628","type":"journal-article","created":{"date-parts":[[2021,10,25]],"date-time":"2021-10-25T15:13:37Z","timestamp":1635174817000},"page":"131-138","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":110,"title":["MIP* = RE"],"prefix":"10.1145","volume":"64","author":[{"given":"Zhengfeng","family":"Ji","sequence":"first","affiliation":[{"name":"University of Technology Sydney, Sydney, Australia"}]},{"given":"Anand","family":"Natarajan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge, MA"}]},{"given":"Thomas","family":"Vidick","sequence":"additional","affiliation":[{"name":"California Institute of Technology, Pasadena, CA"}]},{"given":"John","family":"Wright","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX"}]},{"given":"Henry","family":"Yuen","sequence":"additional","affiliation":[{"name":"Colombia University, New York, NY"}]}],"member":"320","published-online":{"date-parts":[[2021,10,25]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055433"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446810"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060631"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.23.880"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2004.1313847"},{"key":"e_1_2_1_7_1","volume-title":"Ph. D. Thesis","author":"Colbeck R.","year":"2009","unstructured":"Colbeck, R. Quantum and relativistic protocols for secure multi-party computation. Ph. D. Thesis, 2009."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.2307\/1971057"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.67.661"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-2014-12170-8"},{"key":"e_1_2_1_11_1","first-page":"42","article-title":"for polynomials and for approximate functions. In Proceedings of the 23rd STOC. ACM, New York","volume":"32","author":"Gemmel P.","year":"1991","unstructured":"Gemmel, P., Lipton, R., Rubinfeld, R., Sudan, M., Wigderson, A. Self testing\/correcting for polynomials and for approximate functions. In Proceedings of the 23rd STOC. ACM, New York, NY, USA, 1991, 32--42.","journal-title":"NY, USA"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699436"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.11"},{"key":"e_1_2_1_14_1","volume-title":"Quantum soundness of the classical low individual degree test. arXiv preprint arXiv:2009.12982","author":"Ji Z.","year":"2020","unstructured":"Ji, Z., Natarajan, A., Vidick, T., Wright, J., Yuen, H. Quantum soundness of the classical low individual degree test. arXiv preprint arXiv:2009.12982 (2020)."},{"key":"e_1_2_1_15_1","first-page":"3","article-title":"Introduction to Metamathematics","volume":"19","author":"Kleene S.C","year":"1954","unstructured":"Kleene, S.C. Introduction to Metamathematics. J. Symb. Log. 19, 3 (1954), 215--216.","journal-title":"J. Symb. Log."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.65.3373"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 33rd Computational Complexity Conference, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik","author":"Natarajan A.","year":"2018","unstructured":"Natarajan, A., Vidick, T. Two-player entangled games are NP-hard. In Proceedings of the 33rd Computational Complexity Conference, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 2018, 20."},{"key":"e_1_2_1_18_1","volume-title":"arXiv preprint arXiv:1904.05870v3","author":"Natarajan A.","year":"2019","unstructured":"Natarajan, A., Wright, J. NEEXP \u2286 MIP*. arXiv preprint arXiv:1904.05870v3 (2019)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11537-013-1280-5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0375-9601(90)90172-K"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/28907"},{"key":"e_1_2_1_22_1","first-page":"4","article-title":"Some results and problems on quantum bell-type inequalities","volume":"8","author":"Tsirelson B.S","year":"1993","unstructured":"Tsirelson, B.S. Some results and problems on quantum bell-type inequalities. Hadronic J. Suppl. 8, 4 (1993), 329--345.","journal-title":"Hadronic J."},{"key":"e_1_2_1_23_1","volume-title":"Bell inequalities and operator algebras","author":"Tsirelson B.S.","year":"2006","unstructured":"Tsirelson, B.S. Bell inequalities and operator algebras, 2006. Problem statement from website of open problems at TU Braunschweig, 2006. Available at http:\/\/web.archive.org\/web\/20090414083019\/ http:\/\/www.imaph.tu-bs.de\/qi\/problems\/33.html."}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485628","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485628","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:40Z","timestamp":1750191520000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485628"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,25]]},"references-count":23,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["10.1145\/3485628"],"URL":"https:\/\/doi.org\/10.1145\/3485628","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,25]]},"assertion":[{"value":"2021-10-25","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}