| Monday, June 20, 2022 | |
| 9:00 AM | Flajolet lecture: Analytic Information and Learning Theory: From Compression to Learning, by Wojciech Szpankowski (abstract) Philippe always enjoyed our effort to extend analytic combinatorics to information theory. In this talk we first briefly review some results obtained in analytic information theory that led to very precise asymptotics of the minimax redundancy for universal source coding. Then we go beyond this trodden path and attempt to apply analytic tools to some machine learning problems. In particular, we present some new results on regret for online regression with logarithmic loss. |
| 10:00 AM | coffee break |
| 10:30 AM | Automorphisms of Random Trees, by Christoffer Olsson and Stephan Wagner |
| 11:00 AM | Uncovering a Random Tree, by Benjamin Hackl, Alois Panholzer, and Stephan Wagner |
| 11:30 AM | lunch |
| 1:30 PM | Flajolet lecture: The Sum of Powers of Subtree Sizes for Random Trees, by Svante Janson (abstract) Philippe Flajolet had many talents, but he is perhaps best known for his contributions to Analytic Combinatorics using generating functions as a central tool. I, on the other hand, have mostly used other, more probabilistic tools. These different methods should not be seen as enemies, but as friendly complements, that both can help us solve problems that we are interested in. I will illustrate this by talking about some recent (and some not so recent) results on sums of powers of subtree sizes for random trees, in particular conditioned Galton-Watson trees; for this problem, we use both methods: probabilistic methods to prove some results, and generating functions to prove some others. Mainly based on arXiv:2104.02715 (joint work with Jim Fill). |
| 2:30 PM | A Modification of the Random Cutting Model, by Fabian Burghart |
| 3:00 PM | On the Independence Number of Random Trees via Tricolourations, by Etienne Bellin |
| Tuesday, June 21, 2022 | |
| 9:00 AM | Keynote lecture: Counting Walks Confined to a Cone, by Mireille Bousquet-Mélou (abstract) The study of lattice walks confined to cones is a lively topic in enumerative combinatorics, and has witnessed rich developments in the past 20 years. Typically, one is given a finite set of steps $S$ in $Z^d$, and a cone $C$ in $R^d$. Exactly $|S|^n$ walks of length $n$ start from the origin and take their steps in $S$. But how many remain in the cone $C$? One of the motivations for studying such questions is that such walks encode many objects in discrete mathematics, computer science, probability theory, among other fields. In the past 20 years, several approaches have been combined to understand how the choice of the steps and of the cone influence the nature of the counting sequence $a(n)$, or of the the associated series $A(t)=\sum a(n) t^n$. Is $A(t)$ rational, algebraic, or solution of a differential equation? This is now completely understood when $C$ is the first quadrant of the plane and $S$ only consists of "small" steps. This "simple" case involves tools coming from an attractive variety of fields: algebra on formal power series, complex analysis, computer algebra, differential Galois theory. But much remains to be done, for other cones and sets of steps. In particular, the current emphasis is on non-convex cones, typically the three-quadrant cone in two dimensions. |
| 10:00 AM | coffee break |
| 10:30 AM | Universal Properties of Catalytic Variable Equations, by Michael Drmota and Eva-Maria Hainzl |
| 11:00 AM | Enumeration of d-combining Tree-Child Networks, by Yu-Sheng Chang, Michael Fuchs, Hexuan Liu, Michael Wallner, and Guan-Ru Yu |
| 11:30 AM | lunch |
| 1:30 PM | Keynote lecture: Building Sources of Zero Entropy: Rescaling and Inserting Delays, by Brigitte Vallée (abstract) Most of the natural sources that intervene in Information Theory have a positive entropy. They are well studied. The paper aims in building, in an explicit way, natural instances of sources with zero entropy. Such instances are obtained by slowing down sources of positive entropy, with processes which rescale sources or insert delays. These two processes --rescaling or inserting delays-- are essentially the same; they do not change the fundamental intervals of the source, but only the ``depth'' at which they will be used, or the ``speed'' at which they are divided. However, they modify the entropy and lead to sources with zero entropy. The paper begins with a ``starting'' source of positive entropy, and uses a natural class of rescalings of sublinear type. In this way, it builds a class of sources of zero entropy that will be further analysed. As the starting sources possess well understood probabilistic properties, and as the process of rescaling does not change its fundamental intervals, the new sources keep the memory of some important probabilistic features of the initial source. Thus, these new sources may be thoroughly analysed, and their main probabilistic properties precisely described. We focus in particular on two important questions: exhibiting asymptotical normal behaviours à la Shannon-MacMillan-Breiman; analysing the depth of the tries built on the sources. In each case, we obtain a parameterized class of precise behaviours. The paper deals with the analytic combinatorics methodology and makes a great use of generating series. (co-authors: Ali Akhavi and Frédéric Paccaut) |
| 2:30 PM | Random Partitions under the Plancherel-Hurwitz Measure and High Genus Hurwitz Maps, by Guillaume Chapuy, Baptiste Louf, and Harriet Walsh |
| 3:00 PM | Polyharmonic Functions in the Quarter Plane, by Andreas Nessmann |
| Wednesday, June 22, 2022 | |
| 9:00 AM | Keynote lecture: TBA, by Inge Li Gørtz |
| 10:00 AM | coffee break |
| 10:30 AM | Depth-First Search Performance in a Random Digraph with Geometric Degree Distribution, by Philippe Jacquet and Svante Janson |
| 11:00 AM | The Number of Sources and Isolated Vertices in Random Directed Acyclic Graphs, by Dimbinaina Ralaivaosaona |
| 11:30 AM | lunch |
| 1:30 PM | On the Contraction Method with Reduced Independence Assumptions, by Ralph Neininger and Jasmin Straub |
| 2:00 PM | Fragmentation Processes Derived from Conditioned Stable Galton-Watson Trees, by Gabriel Berzunza Ojeda and Cecilia Holmgren |
| 2:30 PM | choice of excursions in Philadelphia for on-site attendees |
| Thursday, June 23, 2022 | |
| 9:00 AM | Keynote lecture: Local limit of random discrete surface with (or without!) a statistical physics model, by Marie Albenque (abstract) Abstract : A planar map is an embedding of a planar graph in the sphere, considered up to deformations. A triangulation is a planar map, where all the faces are triangles. In 2003, in order to define a model of generic planar geometry, Angel and Schramm studied the limit of random triangulations on the sphere. They proved that this model of random maps converges for the Benjamini-Schramm topology, or local topology, towards the now famous Uniform Infinite Planar Triangulation (or UIPT), a probability distribution on infinite triangulations. Soon after, Angel studied some properties of the UIPT. He established that the volume of the balls the UIPT of radius R scales as R^4. Similar results (but with quite different proofs) were then obtained for quadrangulations by Chassaing and Durhuus and Krikun. The results cited above deal with models of maps that fall in the same ``universality class'', identified in the physics literature as the class of ``pure 2D quantum gravity'': the generating series all admit the same critical exponent and the volume of the balls of the local limits of several of those models of random maps are known to grow as R^4.To capture this universal behaviour, a good framework is to consider scaling limits of random maps in the Gromov Hausdorff topology. Indeed, for a wide variety of models the scaling limit exists and is the so-called Brownian sphere, as initially established by Miermont and Le Gall. To escape this pure gravity behaviour, physicists have long ago understood that one should ``couple gravity with matter'', that is, consider models of random maps endowed with a statistical physics model. I will present in particular the case of triangulations decorated by an Ising model. It consists in colouring in black and white the vertices of a triangulation, and consider probability distribution which are now biased by their number of monochromatic edges. In a recent work, in collaboration with Laurent Ménard and Gilles Schaeffer, we proved that the local limit of this model also exists. In this talk, I will try to present these results in the most self-contained way as possible and explain the main ideas underlying their proof, |
| 10:00 AM | coffee break |
| 10:30 AM | Affirmative Sampling: Theory and Applications, by Jérémie Lumbroso and Conrado Martínez |
| 11:00 AM | Partial Match Queries in Quad-K-d Trees, by Amalia Duch and Conrado Martínez |
| 11:30 AM | lunch |
| 1:30 PM | Keynote lecture: Achieving Worst-Case-Optimal Multijoins on Databases through Geometric Data Structures, by Gonzalo Navarro (abstract) The state of the art in database query processing has recently been shaken by a new generation of multi-join processing algorithms with strong optimality guarantees based on the AGM bound of queries: the maximum size of the output of the query over all possible relations with the same cardinalities. Over the years, this has been shown to translate into considerable practical improvements over the classical binary join techniques in use since the sixties. In this talk I will first present the AGM bound, which is quite interesting from an analysis-of-algorithms perspective (even if worst-case). I will then show how it has been typically achieved by following its formula, which has led to the well-known Leapfrog TrieJoin algorithm. Finally, I will introduce a new data structure that regards d-column tables as points in a d-dimensional space and represents those grids using, essentially, d-dimensional versions of quadtrees. The join algorithm is then implemented by (virtually) raising their dimension to include the missing attributes of the join, and then (virtually) traversing their intersection, or equivalently the output space. I will then show how this extremely simple geometric approach does reach worst-case-optimality in a completely different way. This talk is based on our work "Optimal Joins using Compressed Quadtrees", which is to appear in ACM Transactions on Database Systems. |
| 2:30 PM | Parking Functions, Multi-Shuffle, and Asymptotic Phenomena, by Mei Yin |
| 3:00 PM | Business meeting |
| Friday, June 24, 2022 | |
| 9:00 AM | Keynote lecture: TBA, by Rajeev Raman |
| 10:00 AM | coffee break |
| 10:30 AM | Improved Error Bounds for the Number of Irreducible Polynomials and Self-Reciprocal Irreducible Monic Polynomials with Prescribed Coefficients over a Finite Field, by Zhicheng Gao |
| 11:00 AM | Mean Field Analysis of an Incentive Algorithm for a Closed Stochastic Network, by Bianca Marin Moreno, Christine Fricker, Hanene Mohamed, Amaury Philippe, and Martin Trépanier |