Show simple item record

Lower Bound for Constant-Size Local Certification

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorArdévol Martínez, Virginia
hal.structure.identifierLaboratoire des sciences pour la conception, l'optimisation et la production [G-SCOP]
dc.contributor.authorCaoduro, Marco
hal.structure.identifierGraphes, AlgOrithmes et AppLications [GOAL]
dc.contributor.authorFeuilloley, Laurent
HAL ID: 177191
ORCID: 0000-0002-3994-0898
hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
dc.contributor.authorNarboni, Jonathan
ORCID: 0000-0002-3087-5073
hal.structure.identifierLaboratoire de l'Informatique du Parallélisme [LIP]
dc.contributor.authorPournajafi, Pegah
hal.structure.identifierLaboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes [LIMOS]
dc.contributor.authorRaymond, Jean-Florent
dc.date.accessioned2023-01-20T14:47:24Z
dc.date.available2023-01-20T14:47:24Z
dc.date.issued2022
dc.identifier.urihttps://basepub.dauphine.psl.eu/handle/123456789/23792
dc.language.isoenen
dc.subject.ddc003en
dc.titleLower Bound for Constant-Size Local Certificationen
dc.typeCommunication / Conférence
dc.description.abstractenGiven a network property or a data structure, a local certification is a labeling that allows to efficiently check that the property is satisfied, or that the structure is correct. The quality of a certification is measured by the size of its labels: the smaller, the better. This notion plays a central role in self-stabilization, because the size of the certification is a lower bound (and often an upper bound) on the memory needed for silent self-stabilizing construction of distributed data structures.When it comes to the size of the certification labels, one can identify three important regimes: the properties for which the optimal size is polynomial in the number of vertices of the graph, the ones that require only polylogarithmic size, and the ones that can be certified with a constant number of bits. The first two regimes are well studied, with several upper and lower bounds, specific techniques, and active research questions. On the other hand, the constant regime has never been really explored.The main contribution of this paper is the first non-trivial lower bound for this low regime. More precisely, we show that by using certification on just one bit (a binary certification), one cannot certify k-colorability for k≥3. To do so, we develop a new technique, based on the notion of score, and both local symmetry arguments and a global parity argument. We hope that this technique will be useful for establishing stronger results.We complement this result with an upper bound for a related problem, illustrating that in some cases one can do better than the natural upper bound.en
dc.identifier.citationpages239–253en
dc.relation.ispartoftitleStabilization, Safety, and Security of Distributed Systems : 24th International Symposium, SSS 2022, Clermont-Ferrand, Franceen
dc.relation.ispartofpublnameSpringer International Publishingen
dc.relation.ispartofpublcityBerlin Heidelbergen
dc.relation.ispartofdate2022-10
dc.relation.ispartofpages372en
dc.relation.ispartofurl10.1007/978-3-031-21017-4en
dc.identifier.urlsitehttps://arxiv.org/abs/2208.14229en
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-031-21016-7en
dc.relation.conftitle24th International Symposium, International Symposium on Stabilizing, Safety, and Security of Distributed Systems (SSS 2022)en
dc.relation.confdate2022-11
dc.relation.confcityClermont-Ferranden
dc.relation.confcountryFranceen
dc.relation.forthcomingnonen
dc.identifier.doi10.1007/978-3-031-21017-4_16en
dc.description.ssrncandidatenon
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2023-01-20T14:33:35Z
hal.export.arxivnonen
hal.export.pmcnonen
hal.hide.repecnonen
hal.hide.oainonen
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record