{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T18:32:30Z","timestamp":1773858750710,"version":"3.50.1"},"reference-count":21,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/legal\/tdmrep-license"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"publisher","award":["ANR-21-CE48-0014-01"],"award-info":[{"award-number":["ANR-21-CE48-0014-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"publisher","award":["ANR-24-CE48-7768"],"award-info":[{"award-number":["ANR-24-CE48-7768"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"French National Research Agency","doi-asserted-by":"publisher","award":["ANR-11-LABX-0025"],"award-info":[{"award-number":["ANR-11-LABX-0025"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2026,1]]},"DOI":"10.1016\/j.tcs.2025.115643","type":"journal-article","created":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T09:22:28Z","timestamp":1763630548000},"page":"115643","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":0,"special_numbering":"C","title":["Renaming in distributed certification"],"prefix":"10.1016","volume":"1061","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0170-0503","authenticated-orcid":false,"given":"Nicolas","family":"Bousquet","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6200-0514","authenticated-orcid":false,"given":"Louis","family":"Esperet","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3994-0898","authenticated-orcid":false,"given":"Laurent","family":"Feuilloley","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0003-2675-8581","authenticated-orcid":false,"given":"S\u00e9bastien","family":"Zeitoun","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2025.115643_bib0001","series-title":"Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing, PODC 2024","first-page":"429","article-title":"Brief announcement: global certification via perfect hashing","author":"Bousquet","year":"2024"},{"issue":"3","key":"10.1016\/j.tcs.2025.115643_bib0002","article-title":"Introduction to local certification","volume":"23","author":"Feuilloley","year":"2021","journal-title":"Discret. Math. Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2025.115643_bib0003","article-title":"The renaming problem: recent developments and open questions","volume":"117","author":"Alistarh","year":"2015","journal-title":"Bull. EATCS"},{"issue":"4","key":"10.1016\/j.tcs.2025.115643_bib0004","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/s00446-010-0095-3","article-title":"Proof labeling schemes","volume":"22","author":"Korman","year":"2010","journal-title":"Distribut. Comput."},{"key":"10.1016\/j.tcs.2025.115643_bib0005","series-title":"Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5\u20138, 2020","first-page":"1096","article-title":"The power of distributed verifiers in interactive proofs","author":"Naor","year":"2020"},{"key":"10.1016\/j.tcs.2025.115643_bib0006","series-title":"32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15\u201319, 2018","first-page":"25:1","article-title":"Local verification of global proofs","volume":"121","author":"Feuilloley","year":"2018"},{"key":"10.1016\/j.tcs.2025.115643_bib0007","article-title":"Data Structures and Algorithms 1: Sorting and Searching","volume":"1","author":"Mehlhorn","year":"1984"},{"key":"10.1016\/j.tcs.2025.115643_bib0008","series-title":"ACM Symposium on Principles of Distributed Computing, PODC \u201914, Paris, France, July 15\u201318, 2014","first-page":"367","article-title":"On the power of the congested clique model","author":"Drucker","year":"2014"},{"key":"10.1016\/j.tcs.2025.115643_bib0009","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1016\/j.tcs.2018.08.020","article-title":"Approximate proof-labeling schemes","volume":"811","author":"Censor-Hillel","year":"2020","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"10.1016\/j.tcs.2025.115643_bib0010","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1112\/jlms.12781","article-title":"Sparse universal graphs for planarity","volume":"108","author":"Esperet","year":"2023","journal-title":"J. London Math. Soc."},{"key":"10.1016\/j.tcs.2025.115643_bib0011","article-title":"Local certification of forbidden subgraphs","volume":"abs\/2402.12148","author":"Bousquet","year":"2024","journal-title":"CoRR"},{"key":"10.1016\/j.tcs.2025.115643_bib0012","series-title":"21st International Conference on Principles of Distributed Systems, OPODIS 2017, Lisbon, Portugal, December 18\u201320, 2017","first-page":"4:1","article-title":"Deterministic subgraph detection in broadcast CONGEST","volume":"95","author":"Korhonen","year":"2017"},{"key":"10.1016\/j.tcs.2025.115643_bib0013","article-title":"Distributed complexity of Pk-freeness: decision and certification","volume":"abs\/2410.20353","author":"Miyamoto","year":"2024","journal-title":"CoRR"},{"issue":"1","key":"10.1016\/j.tcs.2025.115643_bib0014","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/S0195-6698(81)80015-7","article-title":"Graphs which contain all small graphs","volume":"2","author":"Bollob\u00e1s","year":"1981","journal-title":"Eur. J. Combinator."},{"issue":"3","key":"10.1016\/j.tcs.2025.115643_bib0015","doi-asserted-by":"crossref","first-page":"2181","DOI":"10.1137\/23M1587713","article-title":"Optimal adjacency labels for subgraphs of cartesian products","volume":"38","author":"Esperet","year":"2024","journal-title":"SIAM J. Discret. Math."},{"key":"10.1016\/j.tcs.2025.115643_bib0016","series-title":"33rd International Symposium on Distributed Computing (DISC 2019)","first-page":"13:1","article-title":"Trade-Offs in distributed interactive proofs","volume":"146","author":"Crescenzi","year":"2019"},{"key":"10.1016\/j.tcs.2025.115643_bib0017","unstructured":"I.Z. Ruzsa, E. Szemer\u00e9di, Triple systems with no six points carrying three triangles, 1978, (Combinatorics, Keszthely 1976, Colloq. Math. Soc. J\u00e1nos Bolyai 18, 939\u2013945)."},{"issue":"11","key":"10.1016\/j.tcs.2025.115643_bib0018","doi-asserted-by":"crossref","first-page":"7569","DOI":"10.1109\/TIT.2017.2744608","article-title":"Testing equality in communication graphs","volume":"63","author":"Alon","year":"2017","journal-title":"IEEE Trans. Inf. Theory"},{"key":"10.1016\/j.tcs.2025.115643_bib0019","series-title":"30th Conference on Computational Complexity, CCC\u201915, Portland, OR, USA, June 17\u201319, 2015","first-page":"88","article-title":"Simplified lower bounds on the multiparty communication complexity of disjointness","author":"Rao","year":"2015"},{"key":"10.1016\/j.tcs.2025.115643_bib0020","series-title":"Communication Complexity and Applications","author":"Rao","year":"2020"},{"issue":"3","key":"10.1016\/j.tcs.2025.115643_bib0021","doi-asserted-by":"crossref","first-page":"702","DOI":"10.1137\/23M1557593","article-title":"The approximate degree of DNF and CNF formulas","volume":"54","author":"Sherstov","year":"2025","journal-title":"SIAM J. Comput."}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397525005808?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397525005808?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T11:37:40Z","timestamp":1773833860000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397525005808"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,1]]},"references-count":21,"alternative-id":["S0304397525005808"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2025.115643","relation":{},"ISSN":["0304-3975"],"issn-type":[{"value":"0304-3975","type":"print"}],"subject":[],"published":{"date-parts":[[2026,1]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Renaming in distributed certification","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2025.115643","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2025 Elsevier B.V. All rights are reserved, including those for text and data mining, AI training, and similar technologies.","name":"copyright","label":"Copyright"}],"article-number":"115643"}}