{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:07:07Z","timestamp":1750694827100,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Research Council of Finland","award":["333837"],"award-info":[{"award-number":["333837"]}]},{"name":"German Research Foundation (DFG)","award":["491819048"],"award-info":[{"award-number":["491819048"]}]},{"name":"JSPS KAKENHI","award":["JP20H05966, JP20H04139"],"award-info":[{"award-number":["JP20H05966, JP20H04139"]}]},{"name":"MEXT Q-LEAP","award":["JPMXS0120319794"],"award-info":[{"award-number":["JPMXS0120319794"]}]},{"name":"Helsinki Institute for Information Technology","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Inria","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Swiss National Science Foundation (SNSF)","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649679","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1901-1910","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["No Distributed Quantum Advantage for Approximate Graph Coloring"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7355-4632","authenticated-orcid":false,"given":"Xavier","family":"Coiteux-Roy","sequence":"first","affiliation":[{"name":"TU Munich, Munich, Germany \/ Munich Center for Quantum Science and Technology, Munich, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7498-0660","authenticated-orcid":false,"given":"Francesco","family":"d'Amore","sequence":"additional","affiliation":[{"name":"Aalto University, Espoo, Finland \/ Bocconi University, Milan, Italy"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8726-3465","authenticated-orcid":false,"given":"Rishikesh","family":"Gajjala","sequence":"additional","affiliation":[{"name":"Indian Institute of Science, Bangalore, India \/ Aalto University, Espoo, Finland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1025-5037","authenticated-orcid":false,"given":"Fabian","family":"Kuhn","sequence":"additional","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3721-6553","authenticated-orcid":false,"given":"Fran\u00e7ois","family":"Le Gall","sequence":"additional","affiliation":[{"name":"Nagoya University, Nagoya, Japan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1136-522X","authenticated-orcid":false,"given":"Henrik","family":"Lievonen","sequence":"additional","affiliation":[{"name":"Aalto University, Espoo, Finland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0518-8754","authenticated-orcid":false,"given":"Augusto","family":"Modanese","sequence":"additional","affiliation":[{"name":"Aalto University, Espoo, Finland"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4358-2384","authenticated-orcid":false,"given":"Marc-Olivier","family":"Renou","sequence":"additional","affiliation":[{"name":"Inria, Paris, France \/ Universit\u00e9 Paris-Saclay, Paris, France \/ Institut Polytechnique de Paris, Palaiseau, France"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-7074-2412","authenticated-orcid":false,"given":"Gustav","family":"Schmid","sequence":"additional","affiliation":[{"name":"University of Freiburg, Freiburg, Germany"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6117-8089","authenticated-orcid":false,"given":"Jukka","family":"Suomela","sequence":"additional","affiliation":[{"name":"Aalto University, Espoo, Finland"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.37236\/8395"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2023.10"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1002\/JGT.1005"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2670418.2670440"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63504"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00037"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.DISC.2018.9"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405715"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188860"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31585-5_37"},{"key":"e_1_3_2_1_11_1","volume-title":"YalSAT Entering the SAT Competition","author":"Biere Armin","year":"2017","unstructured":"Armin Biere. 2017. CaDiCaL, Lingeling, Plingeling, Treengeling, YalSAT Entering the SAT Competition 2017. In Proc. of SAT Competition 2017 \u2013 Solver and Benchmark Descriptions, Tom\u00e1\u0161 Balyo, Marijn Heule, and Matti J\u00e4rvisalo (Eds.) (Department of Computer Science Series of Publications B, Vol. B-2017-1). University of Helsinki, 14\u201315."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.1311.2844"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331611"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897570"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087833"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ITCS.2022.35"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.72"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3583668.3594562"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1157957"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2307.09444"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781107338340"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611488"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.DISC.2017.18"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2207.13577"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04355-0_26"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.CH97"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00069"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.166"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1214\/18-ecp118"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1017\/fmp.2016.7"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-94144-8_26"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331628"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2020.23"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212744"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2019.49"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-40970-2_9"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02126799"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3512751"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.73.012112"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486180"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1006\/JCTB.2001.2086"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00493-013-2771-Y"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_3_2_1_46_1","unstructured":"Jukka Suomela. 2023. Open problems related to locality in distributed graph algorithms. https:\/\/jukkasuomela.fi\/open\/"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538413"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2206.02766"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","unstructured":"W. K. Wootters and W. H. Zurek. 1982. A single quantum cannot be cloned. Nature 299 5886 (1982) 802\u2013803. https:\/\/doi.org\/10.1038\/299802a0 10.1038\/299802a0","DOI":"10.1038\/299802a0"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538441"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Vancouver BC Canada","acronym":"STOC '24"},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649679","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649679","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:51Z","timestamp":1750291431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649679"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":50,"alternative-id":["10.1145\/3618260.3649679","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649679","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}