{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:22:51Z","timestamp":1760080971074,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":60,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T00:00:00Z","timestamp":1720396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"UKRI","award":["EP\/X024431\/1"],"award-info":[{"award-number":["EP\/X024431\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,7,8]]},"DOI":"10.1145\/3661814.3662118","type":"proceedings-article","created":{"date-parts":[[2024,6,21]],"date-time":"2024-06-21T12:30:12Z","timestamp":1718973012000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Quantum advantage and CSP complexity"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9491-2016","authenticated-orcid":false,"given":"Lorenzo","family":"Ciardo","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Oxford, Oxford, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,7,8]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.TQC.2017.9"},{"key":"e_1_3_2_1_2_1","volume-title":"42nd International Symposium on Mathematical Foundations of Computer Science. LIPIcs. Leibniz Int. Proc. Inform.","volume":"83","author":"Abramsky Samson","year":"2017","unstructured":"Samson Abramsky, Rui Soares Barbosa, Nadish de Silva, and Octavio Zapata. 2017. The quantum monad on relational structures. In 42nd International Symposium on Mathematical Foundations of Computer Science. LIPIcs. Leibniz Int. Proc. Inform., Vol. 83. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, Art. No. 35, 19."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.48"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.JCSS.2019.05.003"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3265985"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1006507"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1093\/IETFEC\/E89-A.5.1378"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3457606"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2556646"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/130915479"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-017-1621-9"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2007.09.001"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2016.14"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M128212X"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585180"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1312745"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.83.1874"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.26421\/QIC5.45-2"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276713"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/J.TCS.2005.09.028"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.37"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.37236\/999"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exr039"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch86"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585112"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/22M1476435"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch25"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2004.1313847"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_27"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-46135-3_21"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"V\u00edctor Dalmau and Jakub Opr\u0161al. 2023. Local consistency as a reduction between constraint satisfaction problems. (2023). arXiv:2301.05084","DOI":"10.1145\/3661814.3662068"},{"key":"e_1_3_2_1_33_1","volume-title":"Proc. 15th International Joint Conference on Artificial Intelligence (IJCAI'97)","author":"Debruyne Romuald","year":"1997","unstructured":"Romuald Debruyne and Christian Bessi\u00e8re. 1997. Some practicable filtering techniques for the constraint satisfaction problem. In Proc. 15th International Joint Conference on Artificial Intelligence (IJCAI'97). Morgan Kaufmann, 412--417."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_1_35_1","volume-title":"Asian Conference on Quantum Information Science (AQIS'11)","author":"Fukawa Junya","year":"2011","unstructured":"Junya Fukawa, Hiroshi Imai, and Fran\u00e7ois Le Gall. 2011. Quantum coloring games via symmetric SAT games. In Asian Conference on Quantum Information Science (AQIS'11)."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2002.1023373"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321926"},{"key":"e_1_3_2_1_38_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman."},{"volume-title":"The Logico-Algebraic Approach to Quantum Mechanics: Volume I: Historical Evolution","author":"Gleason Andrew M","key":"e_1_3_2_1_39_1","unstructured":"Andrew M Gleason. 1975. Measures on the closed subspaces of a Hilbert space. In The Logico-Algebraic Approach to Quantum Mechanics: Volume I: Historical Evolution. Springer, 123--133."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"volume-title":"Handbook of Linear Algebra","author":"Hogben Leslie","key":"e_1_3_2_1_42_1","unstructured":"Leslie Hogben. 2013. Handbook of Linear Algebra. CRC Press."},{"key":"e_1_3_2_1_43_1","volume-title":"24th Annual IEEE Conference on Computational Complexity","author":"Ito Tsuyoshi","year":"2008","unstructured":"Tsuyoshi Ito, Hirotada Kobayashi, and Keiji Matsumoto. 2008. Oracularization and two-prover one-round interactive proofs against nonlocal strategies. 24th Annual IEEE Conference on Computational Complexity (2008), 217--228."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.11"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263489"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485628"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/090751293"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M117577X"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/20M1378223"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.22364\/BJMC.2016.4.4.16"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.12.009"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2248031"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00039"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(01)00297-7"},{"volume-title":"Quantum Mechanics in Hilbert Space","author":"Prugovecki Eduard","key":"e_1_3_2_1_57_1","unstructured":"Eduard Prugovecki. 1982. Quantum Mechanics in Hilbert Space. Academic Press."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374414"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2178018"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3402029"}],"event":{"name":"LICS '24: 39th Annual ACM\/IEEE Symposium on Logic in Computer Science","sponsor":["SIGLOG ACM Special Interest Group on Logic and Computation","IEEE Computer Society","EACSL"],"location":"Tallinn Estonia","acronym":"LICS '24"},"container-title":["Proceedings of the 39th Annual ACM\/IEEE Symposium on Logic in Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3661814.3662118","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3661814.3662118","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T23:44:09Z","timestamp":1750290249000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3661814.3662118"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,8]]},"references-count":60,"alternative-id":["10.1145\/3661814.3662118","10.1145\/3661814"],"URL":"https:\/\/doi.org\/10.1145\/3661814.3662118","relation":{},"subject":[],"published":{"date-parts":[[2024,7,8]]},"assertion":[{"value":"2024-07-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}