We compare two approaches for modelling imperfect information in infinite games by using finite-state automata. The first, more standard approach views information as the result of an observation process driven by a sequential Mealy machine. In contrast, the second approach features indistinguishability relations described by synchronous two-tape automata.

The indistinguishability-relation model turns out to be strictly more expressive than the one based on observations. We present a characterisation of the indistinguishability relations that admit a representation as a finite-state observation function. We show that the characterisation is decidable, and give a procedure to construct a corresponding Mealy machine whenever one exists.

The talk is based on joint work with Dietmar Berwanger.

In 1980, Edelman defined a poset on objects called noncrossing 2-partitions, made of a partition and a noncrossing partition, with a bijection linking parts of the same size in both partitions. Studying this poset, he proved that the number of noncrossing 2-partitions is given by (n+1)^{n-1}. This is also the number of classical combinatorial objects called parking functions. After introducing noncrossing partitions, noncrossing 2-partitions and parking functions, we will draw the link between parking functions and noncrossing 2-partitions, describing Edelman's poset in terms of parking functions. Afterwards, we will (recall and) use the notion of species introduced in the early 1980s by Joyal to describe the action of the symmetric group on a poset on parking trees.

This is a joint work with Matthieu Josuat-Vergès and Lucas Randazzo.

Post-quantum cryptography is a branch of cryptography that aims at designing non-quantum (i.e. classical) cryptographic systems, which are protected against an adversary possessing a quantum computer. In this thesis, we focus on the study of two fundamental problems for post-quantum cryptography: the shortest vector problem (SVP) and the random subset sum problem. We propose several classical/quantum algorithms that improve the state of the art.

We define a family B(t) of compact subsets of the unit interval which provides a filtration of the set of numbers whose continued fraction expansion has bounded digits. This generalizes to a continuous family the well-known sets of numbers whose continued fraction expansion is bounded above by a fixed integer.

We study how the set B(t) changes as the parameter t ranges in [0,1], and describe precisely the bifurcations that occur as the parameters change. Further, we discuss continuity properties of the Hausdorff dimension of B(t) and its regularity.

Finally, we establish a precise correspondence between these bifurcations and the bifurcations for the classical family of real quadratic polynomials.

Joint with C. Carminati.

Quatrième cours de Frédéric Magniez au Collège de France sur les Algorithmes quantiques (à 10h), suivi d'un exposé de Miklos Santha sur « Le problème du sous-groupe caché » (à 11h30). Informations supplémentaires : https://www.college-de-france.fr/site/frederic-magniez/course-2021-05-12-10h00.htm