Lattice-based cryptography is a very interesting candidate to obtain constructions which resist attacks using a quantum computer. Even if powerful enough quantum computers do not exist yet, it is necessary to be prepared and anticipate their arrival. In this talk, I will introduce lattice-based cryptography and some use of the Rényi divergence in the security proofs. Security proofs allow to prove the security of a cryptographic construction by showing that attacking the scheme is at least as hard as solving a difficult algorithmic problem.

The project of probabilistic programming has long sought to broaden the range of people who benefit from probabilistic inference. But what becomes of probabilistic programming in the age of generative AI? My perspective is influenced by our work at Cogna using AI to transform end users' productivity, by synthesising precision software from requirements. I will survey current progress, and suggest new opportunities for probabilistic programming.

In this talk, I will review a body of recent works aimed at modelling and analysing complex natural systems using (in part) statistical model-checking. The particularity of the systems considered is that they are made up, at least in part, of continuous processes modelled by differential equations. Firstly, I will present results that provide probabilistic guarantees on the statistical verification of these systems despite the errors introduced during the numerical integration of the differential equations, and I will present applications to the parameterization of these models and the analysis of their stability. Secondly, I will present an abstraction of these systems that allows them to be combined with discrete control processes. Finally, I will briefly present two concrete case studies of parametrisation of such models: the growth of the jellyfish Pelagia Noctiluca in the Mediterranean sea and the regrowth of plots of Amazonian forest when subjected to extreme events.

The relationships between probability and machine learning go both ways. In one direction, the classical statistical formulation through random data is probabilistic, but it goes further, with randomness used to speed-up algorithms, e.g., through stochastic gradient descent. More recently, machine learning has been used to propose new frameworks for classical probabilistic tasks such as sampling by denoising. In this talk, I will present an overview of recent advances.

The last five years have seen a revolution in the analysis of the mixing time (i.e., the time required to converge to near-equilibrium) of Markov chains. It is now possible to prove optimal upper bounds on mixing time for a wide variety of Markov chains, including many arising in statistical physics and theoretical computer science. In some instances, no sub-exponential upper bound was previously known. The new ideas that have powered this revolution are strikingly novel, but their working out is often highly technical. I will present recent advances from the point of view of the user. The mixing time bounds can often be packaged in a simple form that hides the technical complexities underneath.

Some of the most extreme examples of the power of randomness in computing come from communication complexity, where shared randomness can allow two parties to solve non-trivial problems with communication cost independent of the input size. The textbook example is the Equality problem, where two parties hold n-bit strings x and y, respectively, and they wish to decide whether x = y. While n bits of deterministic communication are necessary, there is a randomised protocol that communicates only 2 bits. Can we characterise all communication problems that admit such hyperefficient protocols? We discuss recent progress and open problems.

Based on joint work with Yuting Fang, Nathaniel Harms, and Pooya Hatami.

In the fundamental problem of pattern matching, one is given two strings, usually referred to as a pattern and a text, and must decide whether the pattern appears as a substring of the text. In 1970, Knuth, Morris, and Pratt gave the first linear-time and linear-space algorithm for pattern matching. One can argue that this algorithm is optimal: one has to use linear time to read the input and one has to use linear space to store the input. In this talk, we will discuss how probability helped surpass these barriers.