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)

Marius Zimand (Towson University)

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.


Igor Carboni Oliveira (University of Warwick)   Probabilistic Kolmogorov Complexity
Valentin Kabanets (Simon Fraser University)  Derandomization
Bruno Loff (University of Lisbon)   Communication complexity 



Valentino Delle Rose (Pontifical Catholic University of Chile)   Logical depth of infinite binary sequences and its relativization
Noam Greenberg (Victoria University of Wellington)  Convergence properties of Rademacher Series
Rupert Hölzl (University of the Bundeswehr Munich)   Benign approximations and non-speedability
Mathieu Hoyrup (INRIA, Université de Lorraine)  Randomness and computability in dynamical systems
Sophie Laplante (Université Paris Cité)  Certificate games
Jack Lutz (Iowa State University)   Algorithmic Fractal Dimensions
Elvira Mayordomo (University of Zaragoza)   Algorithmic Fractal Dimensions
André Nies (University of Auckland)  Two « almost everywhere » theorems under the lens of algorithmic randomness: Poincare recurrence and Borwein-Ditor
Tatiana Starikovskaya (École Normale Supérieure de Paris)  Approximate membership in formal languages
Tomasz Steifer (Pontifical Catholic University of Chile)   Online learning: from combinatorics to algorithms
Ivan Titov (Heidelberg University)   Convergence speed of Cauchy sequences vs relative randomness of their limits
Nikolay Vereshchagin (HSE University)   Information disclosure in the framework of Kolmogorov complexity
Marius Zimand (Towson University)   Lossless expanders: applications in information theory