Session chair: Hsien-Kuei Hwang

Speaker affiliation: National Taiwan University

Abstract. Stochastic gradient methods are the dominant optimization technique for deep learning, but interestingly they are seldom used in areas other than machine learning. In this talk, we first discuss commonly used stochastic gradient methods and explain why they are more popular for deep learning than other optimization techniques. Next, we check algorithmic issues of stochastic gradient methods, including the convergence properties. Finally, we share some intriguing stories about practical use and present future challenges.

Session chair: Hsien-Kuei Hwang

Speaker affiliation: Academia Sinica

Abstract. The COVID-19 pandemic caused by the SARS-CoV-2 virus has been a defining event of the 21st century, challenging healthcare systems, economies, and societies worldwide. Despite the devastating toll, the pandemic has also spurred a massive global effort to develop vaccines, treatments, and public health interventions. At the onset of the pandemic, Academia Sinica quickly assembled a task force to conduct research on rapid viral detection, antibody screening, drug synthesis, and vaccine development. In this talk, we will discuss the key milestones of the COVID-19 pandemic and highlight the critical role played by data scientists and statisticians in the teamwork at Academia Sinica. We will share lessons learned from this unprecedented global health crisis and how they can inform future research and preparedness efforts.

Session chair: Hsien-Kuei Hwang

Speaker affiliation: Université de Paris 13

Abstract. Multitudinous combinatorial structures are counted by generating functions satisfying a composition scheme $F(z)=G(H(z))$. The corresponding asymptotic analysis becomes challenging when this scheme is critical (i.e., $G$ and~$H$ are simultaneously singular). The singular exponents appearing in the Puiseux expansions of $G$ and $H$ then dictate the asymptotics. In this work, we first complement results of Flajolet et al. For a full family of singular exponents of $G$ and~$H$. Motivated by many examples (random mappings, planar maps, directed lattice paths), we consider a natural extension of this scheme, namely $F(z,u)=G(u H(z))M(z)$. We also consider a variant of this scheme, which allows us to analyse the number of $H$-components of a given size in~$F$. These two models lead to a rich world of limit laws, where we identify the key rôle played by a new universal three-parameter law: the beta-Mittag-Leffler distribution, which is essentially the product of a beta and a Mittag-Leffler distribution. We prove (double) phase transitions, additionally involving Boltzmann and mixed Poisson distributions, with a unified explanation of the associated thresholds. We also obtain moment convergence and local limit theorems. We end with extensions of the critical composition scheme to a cycle scheme and to the multivariate case, leading to product distributions. Applications are presented for random walks, trees (supertrees of trees, increasingly labelled trees, preferential attachment trees),triangular P\'olya urns, and the Chinese restaurant process. Joint work with Markus Kuba and Michael Wallner.

Session chair: Hsien-Kuei Hwang

Speaker affiliation: Vienna University of Technology

Abstract. Multitudinous combinatorial structures are counted by generating functions satisfying a composition scheme $F(z)=G(H(z))$. The corresponding asymptotic analysis becomes challenging when this scheme is critical (i.e., $G$ and~$H$ are simultaneously singular). The singular exponents appearing in the Puiseux expansions of $G$ and $H$ then dictate the asymptotics. In this work, we first complement results of Flajolet et al. For a full family of singular exponents of $G$ and~$H$. Motivated by many examples (random mappings, planar maps, directed lattice paths), we consider a natural extension of this scheme, namely $F(z,u)=G(u H(z))M(z)$. We also consider a variant of this scheme, which allows us to analyse the number of $H$-components of a given size in~$F$. These two models lead to a rich world of limit laws, where we identify the key rôle played by a new universal three-parameter law: the beta-Mittag-Leffler distribution, which is essentially the product of a beta and a Mittag-Leffler distribution. We prove (double) phase transitions, additionally involving Boltzmann and mixed Poisson distributions, with a unified explanation of the associated thresholds. We also obtain moment convergence and local limit theorems. We end with extensions of the critical composition scheme to a cycle scheme and to the multivariate case, leading to product distributions. Applications are presented for random walks, trees (supertrees of trees, increasingly labelled trees, preferential attachment trees),triangular P\'olya urns, and the Chinese restaurant process. Joint work with Markus Kuba and Michael Wallner.

Session chair: Luc Devroye

Speaker affiliation: LIPN, Université Paris 13, Villetaneuse, France

Abstract. In this talk, we will present results obtained in recent years on the combinatorics of the lambda calculus and its interactions with the theory of maps.

Session chair: Luc Devroye

Speaker affiliation: Stellenbosch University

Abstract. We consider the conditioned Galton-Watson tree Tn on n nodes where the offspring distribution $\xi$ satisfies $E(\xi)=1$ and $0<\text{Var}(\xi)<\infty$. We investigate the distributions of various graph-theoretic parameters in $T_n$. Many of these parameters can be computed effectively by making use of some “bottom-up” algorithms on rooted trees, which are processes that go from the leaves to the root of the tree. Examples of such parameters include the independence number, the domination number, the total domination number, and many more. We prove a general theorem for additive parameters of rooted trees which can be used to show that each of these graph-theoretic parameters is asymptotically normal with mean and variance linear in $n$ in the conditioned Galton-Watson tree $T_n$ as n tends to infinity. In this talk, I will describe these bottom-up algorithms and show how they can be used to prove asymptotic normality of the corresponding parameters.

Session chair: Luc Devroye

Speaker affiliation: Johns Hopkins University

Abstract. For a complex number $\alpha$, we consider the sum of the $\alpha$th powers of subtree sizes in Galton–Watson trees conditioned to be of size $n$. Limiting distributions of this functional $X_n(\alpha)$ have been determined for $\text{Re\ }\alpha \neq 0$, revealing a transition between a complex normal limiting distribution for $\text{Re\ } \alpha < 0$ and a non-normal limiting distribution for $\text{Re\ } \alpha > 0$. In this work, we complete the picture by proving a normal limiting distribution, along with moment convergence, in the missing case $\text{Re\ } \alpha = 0$. The same results are also established in the case of the so-called shape functional $X_n'(0)$, which is the sum of the logarithms of all subtree sizes; these results were obtained earlier in special cases. Additionally, we prove convergence of all moments in the case $\text{Re\ } \alpha < 0$, where this result was previously missing, and establish new results about the asymptotic mean for real $\alpha < 1/2$.
A novel feature for $\text{Re\ } \alpha = 0$ is that we find joint convergence for several $\alpha$ to independent limits, in contrast to the cases $\text{Re\ } \alpha \neq 0$, where the limit is known to be a continuous function of $\alpha$. Another difference from the case $\text{Re\ }\alpha \neq 0$ is that there is a logarithmic factor in the asymptotic variance when $\text{Re\ }\alpha = 0$; this holds also for the shape functional.
The proofs are largely based on singularity analysis of generating functions.
This is joint work with Svante Janson and Stephan Wagner.

Session chair: Luc Devroye

Speaker affiliation: National Taiwan University

Abstract. Consider a finite graph and put i.i.d. exponential random weights on the edges. We study the maximum weight matching on the graph, namely the matching such that the total weight is maximized. We show that if the graph is locally tree-like, then the model exhibits a form of correlation decay: if two edges are far apart, then in a certain sense whether they are in the matching will be asymptotically independent. As applications, we show a law of large numbers and a Gaussian central limit theorem for maximum weight matching on uniformly chosen random simple graphs with bounded degree. Based on an ongoing project with Arnab Sen (Minnesota).

ShinYeh Restaurant

Session chair: Bernhard Gittenberger

Speaker affiliation: University of Bath

Abstract. Donsker’s theorem states that a random walk whose step distribution has finite variance converges to a Brownian motion. Similarly, Aldous showed in the early 90's that a Bienaymé-Galton-Watson (BGW) tree whose offspring distribution has finite variance converges to the so-called continuous random tree (CRT). In this talk, I will show a similar result for a BGW tree "in random environment", i.e. in which the offspring distribution depends on the generation of the parent, and is sample for each generation in an i.i.d. way. This is joint work with Guillaume Conchon-Kerjan and Daniel Kious.

Session chair: Bernhard Gittenberger

Speaker affiliation: University of Denver

Abstract. Permutation statistics such as number of descents, major index, and number of inversions have been studied extensively on the entire symmetric group. Less work has been done in specific conjugacy classes. In this talk, we give explicit formulas for first moments of various statistics in conjugacy classes of the symmetric group. We then generalize our method to corresponding statistics on the hyperoctahedral group and discuss some results on higher moments. This is ongoing joint work with Michael Levet, Kevin Liu, Jesse Campion Loth, and Sheila Sundaram.

Session chair: Bernhard Gittenberger

Speaker affiliation: Université Gustave Eiffel

Abstract. The enumeration of linear $\lambda$-terms has attracted quite some attention recently, partly due to their link to combinatorial maps. Zeilberger and Giorgetti (2015) gave a recursive bijection between planar linear normal $\lambda$-terms and planar maps, which, when restricted to 2-connected $\lambda$-terms (i.e., without closed sub-terms), leads to bridgeless planar maps. Inspired by this restriction, Zeilberger and Reed (2019) conjectured that 3-connected planar linear normal $\lambda$-terms have the same counting formula as bipartite planar maps. In this article, we settle this conjecture by giving a direct bijection between these two families. Furthermore, using a similar approach, we give a direct bijection between planar linear normal $\lambda$-terms and planar maps, whose restriction to 2-connected $\lambda$-terms leads to loopless planar maps. This bijection seems different from that of Zeilberger and Giorgetti, even after taking the map dual. We also explore enumerative consequences of our bijections.

Session chair: Bernhard Gittenberger

Speaker affiliation: Vilnius University

Abstract. We derive by a simple elementary approach a full asymptotic expansion for the Stirling numbers of the second kind in the range of parameters that was previously explored by using methods that heavily relied on the use of complex analysis. Our approach relies on exploiting connection between Stirling numbers and finite differences and could probably be extended to the analysis of other problems in which alternating sums of binomial coefficients play important role. We also present an overview of history of the asymptotic estimates of Stirling numbers of the second kind.

Guided tour to National Palace Museum

Session chair: Michael Fuchs

Speaker affiliation: Stanford University

Abstract. Evolutionary biology distinguishes between two types of evolutionary trees with different biological meaning: “species trees”, which represent the descent history of a group of species, and “gene trees”, which represent the descent history of particular genes in the species. The distinction between these biological objects—and the efforts of evolutionary biologists to relate them to one another as part of the field’s major project of inferring evolutionary histories—has generated a rich set of combinatorial structures. This talk will introduce the biological context of gene trees and species trees and will provide a flavor of problems and results on its associated combinatorial structures and their connections to concepts in the analysis of algorithms.

Session chair: Michael Fuchs

Speaker affiliation: National Chengchi University

Abstract. Studying properties of shape statistics for random models which describe the evolutionary relationship between species is an important topic in biology. For phylogenetic trees, which are used to model non-reticulate evolution, many such studies have been performed. On the other hand, for phylogenetic networks, which are used to model reticulate evolution, very little is known about the occurrence of patterns when networks are randomly sampled. In this talk, we will explain our results on limit laws for patterns in ranked tree-child network, a class which was recently introduced by Bienvenu, Lambert, and Steel (2022). Our results extend the limit law for cherries proved by Bienvenu et al. and yield a conjecture for the limit law of any pattern. This is a joint work with Michael Fuchs and Hexuan Liu.

Session chair: Michael Fuchs

Speaker affiliation: Carleton University

Abstract. Hayes equivalence is defined on monic polynomials over a finite field Fq in terms of the prescribed leading coefficients and the residue classes modulo a given monic polynomial Q. We study the distribution of the number of zeros of a random polynomial over finite fields in a given Hayes’ equivalence class. It is well known that the number of distinct zeros of a random polynomial over Fq is asymptotically Poisson with mean 1. We show that this is also true for polynomials in any given Hayes equivalence class provided that the degree of freedom goes to infinity. Asymptotic formulas are also given for the number of such polynomials when the degree of Q and the number of prescribed leading coefficients are small compared with the degree of the polynomial. When the equivalence class is defined by leading coefficients only, the problem is equivalent to the study of the distance distribution over Reed-Solomon codes and our asymptotic formulas extend some earlier results.

Session chair: Michael Fuchs

Speaker affiliation: Normandy University

Abstract. The problem of sampling points of a polytope has been studied extensively from a theoretical and practical point of view. In this talk, we will present several applications covering the study of food webs, the synthesis of random tests for software and the sampling of execution paths for concurrent programs. We will focus on the last application, which has a nice combinatorial interpretation in terms of linear extensions of partially ordered sets.

Session chair: Michael Drmota

Speaker affiliation: Department of Mathematics, Uppsala University, Sweden

Abstract. The study of different models of random trees has been a focus of the AofA community for a long time. Results on the distribution of tree parameters play a key role in the analysis of algorithms and other areas, and it is therefore desirable to develop general methods for this purpose. I will discuss how the notion of additive tree functionals is a unifying tool to obtain limit theorems for a wide variety of tree parameters under different models of randomness. I will illustrate these results with topical examples and applications.

Session chair: Michael Drmota

Speaker affiliation: Goethe University Frankfurt

Abstract. Patricia tries are data structures to index and search words effectively. We show asymptotic normality for additive functionals on patricia tries under rather weak conditions and give formulas for asymptotic means and variances. These results are used to show the asymptotic distribution of random fringe trees of patricia tries, as well as asymptotic normality of some other quantities, such as the independence number. The results build upon related results for tries by Svante Janson by relating additive functionals on patricia tries to those on tries.

Session chair: Michael Drmota

Speaker affiliation: Uppsala University

Abstract. We study the fundamental question of how likely it is that two random trees are isomorphic to each other. We show that the probability decays exponentially for rooted labeled trees as well as Galton--Watson trees with bounded degrees but that this is not true for plane trees, thus providing a counterexample in the general case of Galton--Watson trees without degree restrictions. We also derive limiting distributions for some related parameters: the number of vertices of given degrees in pairs of labeled trees conditioned on being isomorphic, thus showing that they have a different shape than usual labeled trees, as well as the number of labelings and plane representations of Pólya trees. The results rely on both probabilistic and analytic tools.

Session chair: Michael Drmota

Speaker affiliation: Vienna University of Technology

Abstract. We introduce new bijections between different variants of Dyck paths and integer compositions, which seem to be the first of their kind. These variants include, e.g., colored Dyck bridges, Dyck paths with height-labeled peaks, $k$-compositions, as well as $g$-compositions appearing in quantum physics. These bijections explain their very simple and counting formulae~$4^n$, but also allow us to connect different statistics on these objects such as left-to-right maxima and the number of parts. On the one hand, we will subsequently explore the arithmetic properties of Dyck paths via their bijective counterparts in compositions. On the other hand, we will analyze the asymptotic properties and limit laws in compositions via their counterparts in Dyck paths. This is joint work with Michael Wallner.

Session chair: Frédérique Bassino

Speaker affiliation: LIX, École Polytechnique, Palaiseau

Abstract. A heuristic is an algorithm or an algorithm design principle that is used without proven performance guarantees. This heuristic nature suggests that there is little room for theoretical work, but this is not true. For more than thirty years, the mathematical runtime analysis of randomized search heuristics has significantly supported the understanding of these algorithms, has given advice on how to design them and how to set their parameters, and has even proposed new algorithms. In this talk, I give an introduction to this field. I will (i) discuss the differences to classic algorithms analysis, (ii) discuss what makes the analysis of heuristics particularly challenging from the mathematical perspective, (iii) show how such theoretical works have supported the design of heuristics, (iv) discuss some very recent results, and (v) report some classic open problems. This talk assumes no previous knowledge of heuristics.

Session chair: Frédérique Bassino

Speaker affiliation: Vienna University of Technology

Abstract. We provide asymptotics for the number of tree-rooted planar graphs (this is joint work with Marc Noy, Clement Requile and Juanjo Rue)

Session chair: Frédérique Bassino

Speaker affiliation: Vienna University of Technology

Abstract. The study of the asymptotic shape of planar maps has advanced considerably in the past decades, yet the study of prominent graph classes still holds considerable challenges and open problems. In this talk we discuss recent advances for the class of cubic planar graphs, in particular local limits and Gromov-Hausdorff-Prokhorov limits.

Session chair: Frédérique Bassino

Speaker affiliation: Polytechnic University of Catalonia

Abstract. A graph is chordal when every induced cycle of length at least four admits a chord, or equivalently when every separator is a clique. A remarkable class of chordal graphs are the $k$-trees, that are build as follows: start from a $(k + 1)$-clique, add a vertex connected to all vertices of some subclique of size $k$, then repeat this process at will on the resulting graph. Interestingly, this class allows for an alternative definition of tree-width: a graph has tree-width at most $k$ if it is the subgraph of a $k$-tree.
This talk will be about the enumeration of chordal graphs with bounded tree-width. In fact, the asymptotic number of $k$-connected chordal graphs with $n$ labelled vertices and tree-width at most $t$ is of the form $cn^{-5/2}{\gamma}^{n}n!$, for some constants $c$ and $\gamma$ depending on $t$ and $k$. This result is valid for any $t\geq2$ and $0{\leq}k{\leq}t$, and we compute $\gamma$ for small values of $t$. We also obtain a joint normal limiting distribution of the number of $i$-cliques $(i{\leq}t+1)$ of a random graph in this class. Both results fit into the framework of families of graphs that are subcritical.
Joint work with Jordi Castellví, Michael Drmota and Marc Noy.

Session chair: Bruno Salvy

Speaker affiliation: Institut für Mathematik, Alpen-Adria-Universität Klagenfurt

Abstract. Regular Sequences have been introduced by Allouche and Shallit and its elements can be described as matrix products depending on the digit expansion of the index. A prominent example is the sum of digit function; sequences induced by the divide-and-conquer paradigm are also related. We present results on the asymptotic analysis of regular sequences. The result is a sum of periodic fluctuations multiplied by some growth functions; the precision of the asymptotic expansion depends on the joint spectral radius of the matrices involved in the matrix product. We also discuss the frequently encountered special case of recursive sequences. (Based on joint work with Daniel Krenn and Gabriel Lipnik)

Session chair: Bruno Salvy

Speaker affiliation: University of Salzburg

Abstract. In this talk, we consider Stern’s diatomic sequence, the number of non-zero elements in some generalized Pascal's triangle and the number of unbordered factors in the Thue-Morse sequence as running examples. All these sequences can be defined recursively and lead to the concept of so-called $k$-recursive sequences. Here $k$ is an integer and at least 2 (acting somehow as base of a number system), and $k$-recursive sequences are sequences which satisfy a specific type of recurrence relation: Roughly speaking, every subsequence whose indices run through a residue class modulo $k^M$ is a linear combination of subsequences where for each of these subsequences, the indices run through a residue class modulo $k^m$ for some $m < M$.
It turns out that this property is quite natural and many combinatorial sequences are in fact $k$-recursive. We will see that $k$-recursive sequences are related to $k$-regular sequences and a $k$-linear representation of a sequence can be computed easily. Our main focus is the asymptotic behavior of the summatory functions of $k$-recursive sequences. Beside general results, we present a precise asymptotic analysis of our three examples. For the first two sequences, our analysis even leads to precise formulae without error terms.

Session chair: Bruno Salvy

Speaker affiliation: University of Graz

Abstract. Within this hands-on workshop, we explore some recent developments in open-source software in the context of analytic combinatorics. In particular, we focus on the B-term (O-terms with an explicitly given error bound) feature in SageMath's native module for computations with asymptotic expansions, as well as the capabilities of the new sage_acsv package, which allows users to rigorously compute the asymptotic behavior along diagonals of coefficients of a large class of multivariate rational generating functions.

Restaurant (北雲餐廳) inside the Sinica campus (Taiwanese cuisine)

Session chair: Jim Fill

Speaker affiliation: Department of Computer Science, Universitat Politècnica de Catalunya Barcelona, Spain

Abstract. The pioneer work of Flajolet (Probabilistic Counting with G.N. Martin in the mid 80s, the analysis of Adaptive Sampling in the 90s, LogLog and HyperLogLog with M. Durand, É. Fusy et al. in the 2000s) has had tremendous impact in the field of data stream analysis. For example, HyperLogLog is the de facto standard for cardinality estimation in the data analytics industry and routinely used in practice worldwide. Many people in the AofA community have made fundamental contributions to this area: in my talk, I will overview some of these contributions from a historical perspective and convince you of the ample evidence showing that the "AofA approach" to the subject is the right one, following in the wake of Sedgewick's 2016 Flajolet Lecture "Cardinality Estimation" and his more recent talks on HyperBitBit. I will also briefly present a bit of my own contributions (in joint work with Ahmed Helmi, Jérémie Lumbroso and Alfredo Viola) to the area, namely Recordinality, Affirmative Sampling and some on-going work on their applications.

Session chair: Jim Fill

Speaker affiliation: University of Florida

Abstract. We will survey interesting results and open problems from the last four years concerning pattern avoiding permutations. These include the fact that for most patterns, the generating function for the number of permutations avoiding that pattern is not rational. However, the missing case has been missing for four years. One way to prove this result is by the supercritical sequence schema. We will also discuss a non-algebraicity result, and additional open problems.

Session chair: Jim Fill

Speaker affiliation: Johns Hopkins University

Abstract. Given a sequence of i.i.d.\ random vectors uniformly distributed in the $d$-dimensional unit cube $[0, 1]^d$ or unit simplex $\mathcal{S}_d$, we introduce a probabilistic approach to identify, with proofs, the asymptotic conditional distribution of the number of Pareto records broken by the $n$th observation conditionally given that the observation sets a record. Convergence of moments associated with this weak convergence is also established. For general dimension $d$, the limiting distributions are described in terms of Poisson point processes; when $d = 2$, they can be identified precisely in terms of common distributions. A perfect sampling algorithm for the limiting distribution is also proposed. As time permits, several generalizations of our models will also be discussed.
This is joint work with my PhD dissertation advisor, Jim Fill.

Session chair: Jim Fill

Speaker affiliation: Université Sorbonne Paris Nord

Abstract. The $\lambda$-calculus is a formal system that lies at the heart of modern computer science and logic, forming the foundations of various disciplines ranging from proof theory to the development of functional programming languages. This calculus comes equipped with a rewriting rule enabling its use as a computational system. In this talk, we explore the asymptotic behaviour of computations in this system by studying the number of steps required to normalise a large random term. To do so, we employ combinatorial and probabilistic tools that leverage the fact that linear $\lambda$-terms are in bijecion with rooted trivalent maps.