BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//labri.fr//NONSGML kigkonsult.se iCalcreator 2.41.92//
CALSCALE:GREGORIAN
METHOD:PUBLISH
UID:af4e3bdb-d807-4c54-b047-42bde488b276
X-WR-CALNAME:GT AlgoDist\, «Lower Bound for Constant-Size Local Certificati
 on»\, Jonathan Narboni
X-WR-TIMEZONE:Europe/Paris
BEGIN:VTIMEZONE
TZID:Europe/Paris
TZUNTIL:20271031T010000Z
BEGIN:STANDARD
TZNAME:CET
DTSTART:20251026T030000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
RDATE:20261025T030000
END:STANDARD
BEGIN:DAYLIGHT
TZNAME:CEST
DTSTART:20250330T020000
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
RDATE:20260329T020000
RDATE:20270328T020000
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:af4e3bdb-d807-4c54-b047-42bde488b276
DTSTAMP:20260407T192537Z
CLASS:PUBLIC
DESCRIPTION:Jonathan Narboni\n\nTitle: Lower Bound for Constant-Size Local 
 Certification\n\nAbstract:\n\nGiven a network property or a data structure
 \, a local certification is a labeling that allows to efficiently check th
 at the property is satisfied\, or that the structure is correct. The quali
 ty of a certification is measured by the size of its labels: the smaller\,
  the better. This notion plays a central role in self-stabilization\, beca
 use the size of the certification is a lower bound (and often an upper bou
 nd) on the memory needed for silent self-stabilizing construction of distr
 ibuted data structures.\n\nWhen it comes to the size of the certification 
 labels\, one can identify three important regimes: the properties for whic
 h 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 nev
 er been really explored.\n\nThe main contribution of this paper is the fir
 st non-trivial lower bound for this low regime. More precisely\, we show t
 hat 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 techniq
 ue\, 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 e
 stablishing stronger results.\n\nWe complement this result with an upper b
 ound for a related problem\, illustrating that in some cases one can do be
 tter than the natural upper bound.\n\n\n\n\n\nhttps://algodist.labri.fr/in
 dex.php/Main/GT\n\nImport automatique depuis https://webmel.u-bordeaux.fr/
 home/bf-labri.ca@u-bordeaux.fr/gt.algo-dist.ics par sync_icals_to_drupal.p
 y pour gt-algodist
DTSTART;TZID=Europe/Paris:20260202T110000
DTEND;TZID=Europe/Paris:20260202T120000
LOCATION:LaBRI 178
SEQUENCE:0
SUMMARY:GT AlgoDist\, «Lower Bound for Constant-Size Local Certification»\,
  Jonathan Narboni
TRANSP:OPAQUE
END:VEVENT
END:VCALENDAR
