BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//wp-events-plugin.com//7.2.3.1//EN
TZID:Europe/Paris
X-WR-TIMEZONE:Europe/Paris
BEGIN:VEVENT
UID:5071@i2m.univ-amu.fr
DTSTART;TZID=Europe/Paris:20240305T110000
DTEND;TZID=Europe/Paris:20240305T120000
DTSTAMP:20240610T130155Z
URL:https://www.i2m.univ-amu.fr/evenements/majority/
SUMMARY:Diego Maldonado (Concepción): Local Certification of Majority Dyna
 mics
DESCRIPTION:Diego Maldonado: In majority voting dynamics\, a group of n age
 nts in a social network are asked for their preferred candidate in a futur
 e election between two possible choices. At each time step\, a new poll is
  taken\, and each agent adjusts their vote according to the majority opini
 on of their network neighbors. After T time steps\, the candidate with the
  majority of votes is the leading contender in the election.\n\nIn general
 \, it is very hard to predict who will be the leading candidate after a la
 rge number of time-steps.\n\nIn this work\, we study the cost of local cer
 tification for predicting the leading candidate after a certain number of 
 time-steps\, which we call electionpred. We show that in graphs with sub-e
 xponential growth electionpred admits a proof labeling scheme of size O(lo
 g n). We also find non-trivial upper bounds for graphs with a bounded degr
 ee\, in which the size of the certificates are sub-linear in n.\n\nFurther
 more\, we explore lower bounds for the unrestricted case\, showing that lo
 cally checkable proofs for Election-Prediction on arbitrary n-node graphs 
 have certificates on Ω(n) bits.\nFinally\, we show that our upper bounds 
 are tight even for graphs of polynomial growth.
CATEGORIES:Séminaire,Ernest
LOCATION:I2M Luminy - TPR2\, Amphithéâtre Herbrand 130-134 (1er étage)\,
  163 Avenue de Luminy\, Marseille\, 13009\, France
X-APPLE-STRUCTURED-LOCATION;VALUE=URI;X-ADDRESS=163 Avenue de Luminy\, Mars
 eille\, 13009\, France;X-APPLE-RADIUS=100;X-TITLE=I2M Luminy - TPR2\, Amph
 ithéâtre Herbrand 130-134 (1er étage):geo:0,0
END:VEVENT
BEGIN:VTIMEZONE
TZID:Europe/Paris
X-LIC-LOCATION:Europe/Paris
BEGIN:STANDARD
DTSTART:20231029T020000
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
END:STANDARD
END:VTIMEZONE
END:VCALENDAR