AofA: Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms
AofA: méthodes probabilistes, combinatoires et asymptotiques pour l’analyse d’algorithmes
24 – 28 June 2019

Alin Bostan (INRIA Saclay Île-de-France)  Computer algebra for lattice path combinatorics
Classifying lattice walks in restricted lattices is an important problem in enumerative combinatorics. Recently, computer algebra has been used to explore and to solve a number of difficult questions related to lattice walks. We give an overview of recent results on structural properties and explicit formulas for generating functions of walks in the quarter plane, with an emphasis on the algorithmic methodology.

Valentin Féray (University of Zurich)   Limit shapes of random pattern-avoiding permutations
Permutation classes are sets of permutations defined by some forbidden subconfigurations. A lot of effort has been put in the past thirty years to enumerate such sets of permutations. More recently, there has been a growing interest into describing large uniform random permutations in a given class. We will in particular focus on an approach via decomposition trees. Analytic combinatorics plays an important role in analyzing such models. This is joint work with Frédérique Bassino (Paris-Nord), Mathilde Bouvel (Zurich), Lucas Gerin (École Polytechnique), Mickaël Maazoun (ENS de Lyon) and Adeline Pierrot (Orsay).

Peter Mörters (University of Cologne)   Metastability of the contact process on evolving scale-free networks
We study the contact process in the regime of small infection rates on scale-free networks evolving by stationary dynamics. A parameter allows us to interpolate between slow (static) and fast (mean-field) network dynamics. For two paradigmatic classes of networks we investigate transitions between phases of fast and slow extinction and in the latter case we analyse the density of infected vertices in the metastable state. The talk is based on joint work with Emmanuel Jacob (ENS Lyon) and Amitai Linker (Universidad de Chile).

Cyril Nicaud (Université Paris-Est, Marne-la-Vallée)   Realistic analysis of algorithms
In the first part of this talk, we give an analysis of the sorting algorithm TimSort, which is implemented in many popular programming languages such as Python, Java, … In the second part, we present some surprising experimental results on the execution time of basic algorithms run on modern processors. We explain these observations by theoretical analysis of the algorithms taking features of modern achitectures into account. 
Though quite different, both parts try to bridge the gap between textbook algorithms and their « real life » implementations: understanding why TimSort is becoming a very popular sorting algorithm, and how we may have to change our way of analyzing algorithms considering the progresses made in computer architecture.

Robin Pemantle (University of Pennsylvania)   Effective algorithms in ACSV
I will begin by reviewing the essentials of analytic combinatorics in several variables (ACSV), highlighting the steps that have up to now required human intervention: finding the dominating point, proving minimality, contour deformation. The rest of the talk will be about effective solutions to these problems. These include rigorizing the Morse theoretic underpinnings of ACSV, using computer algebra to find critical points at infinity, complex variable methods that work for symmetric functions, and some work in progress on a general topological method for smooth denominators. For some audience members, the talk will be uncomfortably topological. On the other hand, I will include a lot of pictures, so the topology can be understood without much formal background.

Dana Randall (Georgia Institute of Technology)   Sampling algorithms and phase transitions
Markov chain Monte Carlo methods have become ubiquitous across science and engineering to model dynamics and explore large combinatorial sets. Over the last 20 years there have been tremendous advances in the design and analysis of efficient sampling algorithms for this purpose. One of the striking discoveries has been the realization that many natural Markov chains undergo phase transitions, whereby they abruptly change from being efficient to inefficient as some parameter of the system is modified. Generating functions can offer an alternative approach to sampling and they play a role in showing when certain Markov chains are efficient or not. We will explore the interplay between Markov chains, generating functions, and phase transitions for a variety of combinatorial problems, including graded posets, Boltzmann sampling, and 3-colorings on Z^2.

Andrea Sportiello (CNRS/ Université Paris 13)   The challenge of linear-time Boltzmann sampling
Let X_N be an ensemble of combinatorial structures of size N, equipped with a measure. Consider the algorithmic problem of exactly sampling from this measure. When this ensemble has a `combinatorial specification’, the celebrated Boltzmann sampling algorithm allows to solve this problem with a complexity which is, typically, of order N^(3/2). Here, a factor N is inherent to the problem, and implied by the Shannon bound on the average number of required random bits, while the extra factor N^(1/2) is due to the fact that Boltzmann sampling produces a random object in the union of the (X_n)’s, whose size is a random variable, valued N only with probability of order N^(-1/2). How much can we improve on this complexity? And in which generality? As you can imagine, in the state of the art there is a trade-off between generality and overall complexity. We will review some recent ideas which explore various directions in this balance.

Lenka Zdeborová (CNRS/ CEA Saclay​)  Optimal algorithms in inference inspired by statistical physics
Analysis of algorithms in noisy high-dimensional probabilistic problems poses many current challenges. In a subclass of these problems the corresponding challenges can be overcome with the help of a method coming from statistical mechanics. I will review some of the related recent work together with progress on rigorous justification of the corresponding results.