{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T23:26:00Z","timestamp":1775345160402,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":32,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585208","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1603-1616","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Quantum Free Games"],"prefix":"10.1145","author":[{"given":"Anand","family":"Natarajan","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tina","family":"Zhang","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a001"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.13"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/278298.278306"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273901"},{"key":"e_1_3_2_1_5_1","volume-title":"Non-deterministic exponential time has two-prover interactive protocols. Computational complexity, 1, 1","author":"Babai L\u00e1szl\u00f3","year":"1991","unstructured":"L\u00e1szl\u00f3 Babai , Lance Fortnow , and Carsten Lund . 1991. Non-deterministic exponential time has two-prover interactive protocols. Computational complexity, 1, 1 ( 1991 ), 3\u201340. L\u00e1szl\u00f3 Babai, Lance Fortnow, and Carsten Lund. 1991. Non-deterministic exponential time has two-prover interactive protocols. Computational complexity, 1, 1 (1991), 3\u201340."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055433"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICQNM.2009.21"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Fernando Brand\u00e3o Matthias Christandl and John Yard. 2010. A quasipolynomial-time algorithm for the quantum separability problem. arxiv:1011.2751. \t\t\t\t  Fernando Brand\u00e3o Matthias Christandl and John Yard. 2010. A quasipolynomial-time algorithm for the quantum separability problem. arxiv:1011.2751.","DOI":"10.1145\/1993636.1993683"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488718"},{"key":"e_1_3_2_1_10_1","unstructured":"J. Chen and A. Drucker. 2010. Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements. arxiv:1011.0716. \t\t\t\t  J. Chen and A. Drucker. 2010. Short Multi-Prover Quantum Proofs for SAT without Entangled Measurements. arxiv:1011.0716."},{"key":"e_1_3_2_1_11_1","volume-title":"Forbes","author":"Chiesa Alessandro","year":"2011","unstructured":"Alessandro Chiesa and Michael J . Forbes . 2011 . Improved Soundness for QMA with Multiple Provers . arxiv:1108.2098. Alessandro Chiesa and Michael J. Forbes. 2011. Improved Soundness for QMA with Multiple Provers. arxiv:1108.2098."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1009378.1009560"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms15485"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Matthew Coudron and Henry Yuen. 2013. Infinite Randomness Expansion and Amplification with a Constant Number of Devices. arxiv:1310.6755. \t\t\t\t  Matthew Coudron and Henry Yuen. 2013. Infinite Randomness Expansion and Amplification with a Constant Number of Devices. arxiv:1310.6755.","DOI":"10.1145\/2591796.2591873"},{"key":"e_1_3_2_1_15_1","unstructured":"Mikael de la Salle. 2022. Spectral gap and stability for groups and non-local games. arxiv:2204.07084. \t\t\t\t  Mikael de la Salle. 2022. Spectral gap and stability for groups and non-local games. arxiv:2204.07084."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0098-3"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-2014-12170-8"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2022-01-03-614"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432625"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.11"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055441"},{"key":"e_1_3_2_1_22_1","unstructured":"Zhengfeng Ji Anand Natarajan Thomas Vidick John Wright and Henry Yuen. 2020. MIP^* = RE. arxiv:2001.04383. \t\t\t\t  Zhengfeng Ji Anand Natarajan Thomas Vidick John Wright and Henry Yuen. 2020. MIP^* = RE. arxiv:2001.04383."},{"key":"e_1_3_2_1_23_1","volume-title":"Derandomizing Arthur\u2013Merlin games using hitting sets. computational complexity, 14, 3","author":"Miltersen Peter Bro","year":"2005","unstructured":"Peter Bro Miltersen and N Variyam Vinodchandran . 2005. Derandomizing Arthur\u2013Merlin games using hitting sets. computational complexity, 14, 3 ( 2005 ), 256\u2013279. Peter Bro Miltersen and N Variyam Vinodchandran. 2005. Derandomizing Arthur\u2013Merlin games using hitting sets. computational complexity, 14, 3 (2005), 256\u2013279."},{"key":"e_1_3_2_1_24_1","volume-title":"Seyed Sajjad Nezhadi, and Henry Yuen","author":"Mousavi Hamoon","year":"2020","unstructured":"Hamoon Mousavi , Seyed Sajjad Nezhadi, and Henry Yuen . 2020 . On the complexity of zero gap MIP^*. arxiv:2002.10490. Hamoon Mousavi, Seyed Sajjad Nezhadi, and Henry Yuen. 2020. On the complexity of zero gap MIP^*. arxiv:2002.10490."},{"key":"e_1_3_2_1_25_1","volume-title":"Seyed Sajjad Nezhadi, and Henry Yuen","author":"Mousavi Hamoon","year":"2021","unstructured":"Hamoon Mousavi , Seyed Sajjad Nezhadi, and Henry Yuen . 2021 . Nonlocal Games, Compression Theorems and the Arithmetical Hierarchy . arxiv:2110.04651. Hamoon Mousavi, Seyed Sajjad Nezhadi, and Henry Yuen. 2021. Nonlocal Games, Compression Theorems and the Arithmetical Hierarchy. arxiv:2110.04651."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.CCC.2018.20"},{"key":"e_1_3_2_1_27_1","volume-title":"2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). 510\u2013518","author":"Natarajan Anand","year":"2019","unstructured":"Anand Natarajan and John Wright . 2019 . NEEXP \u2286 MIP^* . In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). 510\u2013518 . arxiv:1904.05870. Anand Natarajan and John Wright. 2019. NEEXP \u2286 MIP^*. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). 510\u2013518. arxiv:1904.05870."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"crossref","unstructured":"Michael A Nielsen and Isaac Chuang. 2002. Quantum computation and quantum information. \t\t\t\t  Michael A Nielsen and Isaac Chuang. 2002. Quantum computation and quantum information.","DOI":"10.1119\/1.1463744"},{"key":"e_1_3_2_1_29_1","volume-title":"Classical command of quantum systems. Nature, 496, 7446","author":"Reichardt Ben W","year":"2013","unstructured":"Ben W Reichardt , Falk Unger , and Umesh Vazirani . 2013. Classical command of quantum systems. Nature, 496, 7446 ( 2013 ), 456. arxiv:1209.0448. Ben W Reichardt, Falk Unger, and Umesh Vazirani. 2013. Classical command of quantum systems. Nature, 496, 7446 (2013), 456. arxiv:1209.0448."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-09-30-337"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11672142_12"},{"key":"e_1_3_2_1_32_1","unstructured":"Mark M Wilde. 2011. From classical to quantum Shannon theory. arXiv preprint arXiv:1106.1445 arxiv:1106.1445. \t\t\t\t  Mark M Wilde. 2011. From classical to quantum Shannon theory. arXiv preprint arXiv:1106.1445 arxiv:1106.1445."}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585208","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:01Z","timestamp":1750178821000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":32,"alternative-id":["10.1145\/3564246.3585208","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585208","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}