BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen - ECPv5.7.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
X-ORIGINAL-URL:https://www.greyc.fr
X-WR-CALDESC:évènements pour GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20250330T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20251026T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20250128T104500
DTEND;TZID=Europe/Paris:20250128T114500
DTSTAMP:20260421T154322
CREATED:20250127T162127Z
LAST-MODIFIED:20250127T162310Z
UID:11779-1738061100-1738064700@www.greyc.fr
SUMMARY:Séminaire Algorithmique : Geoffroy Caillat-Grenier (LIRMM\, Univ. Montpellier)\, « From combinatorics of graphs to communication complexity in algorithmic information theory »
DESCRIPTION:Several connexions between information theory and combinatorics of graphs have been explored in the last decades. Following this path\, we use tools from spectral graph theory to show impossibility results in information theoretic cryptography. We place ourselves in the Kolmogorov complexity framework. After a short introduction to algorithmic information theory and secret key agreement\, we will study some spectral and combinatorial properties of bipartite graphs explicitly constructed. \nThose graphs can represent the inputs for a communication problem. Spectral and combinatorial properties of these objects imply information  inequalities that make impossible some communication protocols for secret key agreement. For instance\, if the graph representing the inputs of the secret key agreement is a spectral expander\, we get the worst case in terms of communication complexity. Moreover\, the communication protocol is inherently uneven: for two participants\, only one of them needs to send all the needed information. Theses facts are connected to the mutual information unextractability phenomenon.
URL:https://www.greyc.fr/event/seminaire-algorithmique-geoffroy-caillat-grenier-lirmm-univ-montpellier-from-combinatorics-of-graphs-to-communication-complexity-in-algorithmic-information-theory/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,News,Séminaire Algo
END:VEVENT
END:VCALENDAR