{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,6]],"date-time":"2025-10-06T18:50:14Z","timestamp":1759776614499,"version":"3.40.3"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783031210167"},{"type":"electronic","value":"9783031210174"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-21017-4_16","type":"book-chapter","created":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T18:06:34Z","timestamp":1667930794000},"page":"239-253","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Lower Bound for\u00a0Constant-Size Local Certification"],"prefix":"10.1007","author":[{"given":"Virgina","family":"Ard\u00e9vol Mart\u00ednez","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Caoduro","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3994-0898","authenticated-orcid":false,"given":"Laurent","family":"Feuilloley","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3087-5073","authenticated-orcid":false,"given":"Jonathan","family":"Narboni","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pegah","family":"Pournajafi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4646-7602","authenticated-orcid":false,"given":"Jean-Florent","family":"Raymond","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,11,9]]},"reference":[{"issue":"6","key":"16_CR1","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s00446-020-00373-4","volume":"33","author":"A Abboud","year":"2020","unstructured":"Abboud, A., Censor-Hillel, K., Khoury, S., Lenzen, C.: Fooling views: a new lower bound technique for distributed computations under congestion. Distrib. Comput. 33(6), 545\u2013559 (2020). https:\/\/doi.org\/10.1007\/s00446-020-00373-4","journal-title":"Distrib. Comput."},{"key":"16_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/3-540-54099-7_2","volume-title":"Distributed Algorithms","author":"Y Afek","year":"1991","unstructured":"Afek, Y., Kutten, S., Yung, M.: Memory-efficient self stabilizing protocols for general networks. In: van Leeuwen, J., Santoro, N. (eds.) WDAG 1990. LNCS, vol. 486, pp. 15\u201328. Springer, Heidelberg (1991). https:\/\/doi.org\/10.1007\/3-540-54099-7_2"},{"issue":"1","key":"16_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-031-02009-4","volume":"4","author":"L Barenboim","year":"2013","unstructured":"Barenboim, L., Elkin, M.: Distributed graph coloring: fundamentals and recent developments. Synth. Lect. Distrib. Comput. Theory 4(1), 1\u2013171 (2013)","journal-title":"Synth. Lect. Distrib. Comput. Theory"},{"key":"16_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1007\/978-3-319-11764-5_2","volume-title":"Stabilization, Safety, and Security of Distributed Systems","author":"L Blin","year":"2014","unstructured":"Blin, L., Fraigniaud, P., Patt-Shamir, B.: On proof-labeling schemes versus silent self-stabilizing algorithms. In: Felber, P., Garg, V. (eds.) SSS 2014. LNCS, vol. 8756, pp. 18\u201332. Springer, Cham (2014). https:\/\/doi.org\/10.1007\/978-3-319-11764-5_2"},{"key":"16_CR5","unstructured":"Bousquet, N., Feuilloley, L., Pierron, T.: Local certification of graph decompositions and applications to minor-free classes. In: OPODIS 2021, vol. 217, pp. 22:1\u201322:17 (2021)"},{"key":"16_CR6","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/j.tcs.2018.08.020","volume":"811","author":"K Censor-Hillel","year":"2020","unstructured":"Censor-Hillel, K., Paz, A., Perry, M.: Approximate proof-labeling schemes. Theor. Comput. Sci. 811, 112\u2013124 (2020)","journal-title":"Theor. Comput. Sci."},{"key":"16_CR7","unstructured":"Crescenzi, P., Fraigniaud, P., Paz, A.: Trade-offs in distributed interactive proofs. In DISC 2019, vol. 146, pp. 13:1\u201313:17 (2019)"},{"key":"16_CR8","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.tcs.2022.01.023","volume":"909","author":"L Esperet","year":"2022","unstructured":"Esperet, L., L\u00e9v\u00eaque, B.: Local certification of graphs on surfaces. Theor. Comput. Sci. 909, 68\u201375 (2022)","journal-title":"Theor. Comput. Sci."},{"key":"16_CR9","doi-asserted-by":"crossref","unstructured":"Feuilloley, L.: Introduction to local certification. Discret. Math. Theor. Comput. Sci. 23(3) (2021)","DOI":"10.46298\/dmtcs.6280"},{"key":"16_CR10","doi-asserted-by":"crossref","unstructured":"Feuilloley, L., Bousquet, N., Pierron, T.: What can be certified compactly? compact local certification of MSO properties in tree-like graphs. In: PODC\u201922, pp. 131\u2013140. ACM (2022)","DOI":"10.1145\/3519270.3538416"},{"issue":"2","key":"16_CR11","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/s00446-020-00386-z","volume":"34","author":"L Feuilloley","year":"2020","unstructured":"Feuilloley, L., Fraigniaud, P., Hirvonen, J., Paz, A., Perry, M.: Redundancy in distributed proofs. Distrib. Comput. 34(2), 113\u2013132 (2020). https:\/\/doi.org\/10.1007\/s00446-020-00386-z","journal-title":"Distrib. Comput."},{"key":"16_CR12","unstructured":"Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., R\u00e9mila, E., Todinca, I.: Local certification of graphs with bounded genus. CoRR, abs\/2007.08084 (2020)"},{"issue":"7","key":"16_CR13","doi-asserted-by":"publisher","first-page":"2215","DOI":"10.1007\/s00453-021-00823-w","volume":"83","author":"L Feuilloley","year":"2021","unstructured":"Feuilloley, L., Fraigniaud, P., Montealegre, P., Rapaport, I., R\u00e9mila, \u00c9., Todinca, I.: Compact distributed certification of planar graphs. Algorithmica 83(7), 2215\u20132244 (2021)","journal-title":"Algorithmica"},{"key":"16_CR14","unstructured":"Fischer, O., Oshman, R., Shamir, D.: Explicit space-time tradeoffs for proof labeling schemes in graphs with small separators. In: OPODIS 2021, vol. 217, pp. 21:1\u201321:22 (2021)"},{"key":"16_CR15","doi-asserted-by":"crossref","unstructured":"Fraigniaud, P., Heinrich, M., Kosowski, A.: Local conflict coloring. In: Dinur, I., (ed.) FOCS 2016, pp. 625\u2013634 (2016)","DOI":"10.1109\/FOCS.2016.73"},{"key":"16_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-09993-9_7","volume-title":"Structural Information and Communication Complexity","author":"P Fraigniaud","year":"2022","unstructured":"Fraigniaud, P., Montealegre, P., Rapaport, I., Todinca, I.: A meta-theorem for distributed certification. In: Parter, M. (ed.) SIROCCO 2022. LNCS, vol. 13298. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-09993-9_7"},{"issue":"1","key":"16_CR17","first-page":"1","volume":"12","author":"M G\u00f6\u00f6s","year":"2016","unstructured":"G\u00f6\u00f6s, M., Suomela, J.: Locally checkable proofs in distributed computing. Theory Comput. 12(1), 1\u201333 (2016)","journal-title":"Theory Comput."},{"issue":"4","key":"16_CR18","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/s00446-007-0025-1","volume":"20","author":"A Korman","year":"2007","unstructured":"Korman, A., Kutten, S.: Distributed verification of minimum spanning trees. Distrib. Comput. 20(4), 253\u2013266 (2007)","journal-title":"Distrib. Comput."},{"issue":"4","key":"16_CR19","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s00446-010-0095-3","volume":"22","author":"A Korman","year":"2010","unstructured":"Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. Distrib. Comput. 22(4), 215\u2013233 (2010)","journal-title":"Distrib. Comput."},{"key":"16_CR20","unstructured":"Maus, Y., Tonoyan, T.: Local conflict coloring revisited: linial for lists. In: Attiya, H. (ed.) DISC 2020, vol. 179, pp. 16:1\u201316:18 (2020)"},{"issue":"6","key":"16_CR21","doi-asserted-by":"publisher","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.J.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"key":"16_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1007\/978-3-319-72050-0_4","volume-title":"Structural Information and Communication Complexity","author":"R Ostrovsky","year":"2017","unstructured":"Ostrovsky, R., Perry, M., Rosenbaum, W.: Space-time tradeoffs for distributed verification. In: Das, S., Tixeuil, S. (eds.) SIROCCO 2017. LNCS, vol. 10641, pp. 53\u201370. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-72050-0_4"},{"issue":"3","key":"16_CR23","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1145\/3427361.3427374","volume":"51","author":"J Suomela","year":"2020","unstructured":"Suomela, J.: Using round elimination to understand locality. SIGACT News 51(3), 63\u201381 (2020)","journal-title":"SIGACT News"}],"container-title":["Lecture Notes in Computer Science","Stabilization, Safety, and Security of Distributed Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-21017-4_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,8]],"date-time":"2022-11-08T18:08:23Z","timestamp":1667930903000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-21017-4_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031210167","9783031210174"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-21017-4_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"9 November 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SSS","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on Stabilizing, Safety, and Security of Distributed Systems","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Clermont-Ferrand","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 November 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 November 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sss2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sss2022.limos.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}