For a new seminar of the proofs and algorithms pole of LIX, we are happy to welcome Benoit Monin.

Abstract: La complexité de Kolmogorov est utilisée avec succès pour caractériser l’aléatoire pour les chaînes binaires infinies : Il s’agit des chaînes dont la complexité de Kolmogorov de leurs préfixes est maximale. A l’opposé, les chaînes binaires infinies dites “K-triviales” sont celles dont la complexité de Kolmogorov de leurs préfixes est minimale. La classe des K-triviaux est dénombrable, et contient “juste un peu plus” que les chaînes binaires infinies calculables. Les nombreuses études sur les K-triviaux depuis une vingtaine d’années ont révélé la grande richesse de cette classe. Nous en présenterons les différents aspects.

Link to the online conference

Next seminar will be on Thursday 08 April 2021 at 14h30 by Jana Burman: Time-Optimal Self-Stabilizing Leader Election in Population Protocols.

The list of next seminars can be found at: https://smimram.gitlabpages.inria.fr/proofs-algorithms/seminar/

The calendar of seminars can be found at: https://smimram.gitlabpages.inria.fr/proofs-algorithms/seminar.ics