{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:12:19Z","timestamp":1787508739211,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":25,"publisher":"ACM","funder":[{"name":"Research Council of Finland","award":["363558"],"award-info":[{"award-number":["363558"]}]},{"name":"Research Council of Finland","award":["359104"],"award-info":[{"award-number":["359104"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,16]]},"DOI":"10.1145\/3732772.3733546","type":"proceedings-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T10:23:34Z","timestamp":1749810214000},"page":"379-382","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Brief Announcement: Strong and Hiding Distributed Certification of $k$-Coloring"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0518-8754","authenticated-orcid":false,"given":"Augusto","family":"Modanese","sequence":"first","affiliation":[{"name":"Aalto University, Espoo, Finland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2508-5907","authenticated-orcid":false,"given":"Pedro","family":"Montealegre","sequence":"additional","affiliation":[{"name":"Adolfo Ib\u00e1\u00f1ez University, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0339-0182","authenticated-orcid":false,"given":"Mart\u00edn","family":"R\u00edos-Wilson","sequence":"additional","affiliation":[{"name":"Adolfo Ib\u00e1\u00f1ez University, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czech Republic, June 23\u201327","author":"Akbari Amirreza","year":"2025","unstructured":"Amirreza Akbari, Xavier Coiteux-Roy, Francesco D'Amore, Fran\u00e7ois Le Gall, Henrik Lievonen, Darya Melnyk, Augusto Modanese, Shreyas Pai, Marc-Olivier Renou, V\u00e1clav Rozho\u0148, and Jukka Suomela. 2025. Online Locality Meets Distributed Quantum Computing. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czech Republic, June 23\u201327, 2025. ACM. arXiv:2403.01903"},{"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","volume-title":"Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czech Republic, June 23\u201327","author":"Balliu Alkida","year":"2025","unstructured":"Alkida Balliu, Sebastian Brandt, Xavier Coiteux-Roy, Francesco d'Amore, Massimo Equi, Fran\u00e7ois Le Gall, Henrik Lievonen, Augusto Modanese, Dennis Olivetti, Marc-Olivier Renou, Jukka Suomela, Lucas Tendick, and Isadora Veeren. 2025. Distributed Quantum Advantage for Local Problems. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Prague, Czech Republic, June 23\u201327, 2025. ACM. arXiv:2411.03240 https:\/\/arxiv.org\/abs\/2411.03240"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3461458"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405715"},{"key":"e_1_3_2_1_6_1","volume-title":"52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025","author":"Balliu Alkida","year":"2025","unstructured":"Alkida Balliu, Mohsen Ghaffari, Fabian Kuhn, Augusto Modanese, Dennis Olivetti, Mika\u00ebl Rabie, Jukka Suomela, and Jara Uitto. 2025. Shared Randomness Helps with Local Distributed Problems. In 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, July 8\u201311, 2025, Aarhus, Denmark. arXiv:2407.05445 https:\/\/arxiv.org\/abs\/2407.05445"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.97"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2024.21"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897570"},{"key":"e_1_3_2_1_10_1","volume-title":"Near-Optimal Resilient Labeling Schemes. In 28th International Conference on Principles of Distributed Systems (OPODIS","author":"Censor-Hillel Keren","year":"2025","unstructured":"Keren Censor-Hillel and Einav Huberman. 2025. Near-Optimal Resilient Labeling Schemes. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik, 35\u20131."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1117537"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3662158.3662794"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1157957"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649679"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.DISC.2017.18"},{"key":"e_1_3_2_1_16_1","volume-title":"25th International Conference on Principles of Distributed Systems (OPODIS","author":"Fischer Orr","year":"2022","unstructured":"Orr Fischer, Rotem Oshman, and Dana Shamir. 2022. Explicit space-time tradeoffs for proof labeling schemes in graphs with small separators. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00069"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055471"},{"key":"e_1_3_2_1_19_1","first-page":"1","article-title":"Locally checkable proofs in distributed computing","volume":"12","author":"G\u00f6\u00f6s Mika","year":"2016","unstructured":"Mika G\u00f6\u00f6s and Jukka Suomela. 2016. Locally checkable proofs in distributed computing. Theory of Computing 12 (2016), 1\u201333.","journal-title":"Theory of Computing"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2502.07594"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2019.49"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2502.13854"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"}],"event":{"name":"PODC '25: ACM Symposium on Principles of Distributed Computing","location":"Hotel Las Brisas Huatulco Huatulco Mexico","acronym":"PODC '25","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3732772.3733546","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T10:26:01Z","timestamp":1749810361000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3732772.3733546"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,13]]},"references-count":25,"alternative-id":["10.1145\/3732772.3733546","10.1145\/3732772"],"URL":"https:\/\/doi.org\/10.1145\/3732772.3733546","relation":{},"subject":[],"published":{"date-parts":[[2025,6,13]]},"assertion":[{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}