CONFERENCE
Randomness, Information & Complexity
Aléatoire, information et complexité
19 – 23 February, 2024
Scientific Committee
Comité scientifique
Laurent Bienvenu (CNRS, Université de Bordeaux)
Michal Koucky (Charles University)
Elvira Mayordomo (University of Zaragoza)
Wolfgang Merkle (Heidelberg University)
Sylvain Périfel (Université Paris Cité)
Andrei Romashchenko (CNRS, Université de Montpellier)
Alexander Shen (CNRS, Université de Montpellier)
Organizing Committee
Comité d’organisation
Laurent Bienvenu (CNRS, Université de Bordeaux)
Sylvain Périfel (Université Paris Cité)
Andrei Romaschenko (CNRS, Université de Montpellier)
Alexander Shen (CNRS, Université de Montpellier)
Guillaume Theyssier (CNRS, Aix-Marseille Université)
Various connections between information and computation theory are studied since many decades. A notion of algorithmic (Kolmogorov) complexity that uses computation theory to measure information in finite objects (instead of random variables) appeared in 1960s and became by now a standard tool. There are many examples of problems where information-theoretic tools like Shannon’s entropy were used to analyze complexity of algorithms and prove lower bounds. Now, several directions of research based on theses connections are currently active: communication and information complexity, complexity and dimensions, complexity vs compression, pseudo-random structures, complexity of computation and Kolmogorov complexity, and randomness and computability theory. The goal of this week is to gather experts from all of these directions, who share a common general view on randomness, information and complexity.
SPEAKERS
Noam Greenberg (Victoria University of Wellington)
Mathieu Hoyrup (INRIA, Université de Lorraine)
Valentin Kabanets (Simon Fraser University)
Sophie Laplante (Université Paris Cité)
Jack Lutz (Iowa State University)
André Nies (University of Auckland)
Igor Oliveira (University of Warwick)
Adi Shraibman (Academic College of Tel-Aviv-Yaffo)
Tatiana Starikovskaya (École Normale Supérieure de Paris)