AofA 2022

33rd International Conference on
Probabilistic, Combinatorial and Asymptotic Methods
for the Analysis of Algorithms (AofA 2022)

Dates

20 June 2022 (Monday) through 24 June 2022 (Friday)

Location

David Rittenhouse Laboratory
University of Pennsylvania
Philadelphia, PA (Philadelphia city homepage; tourism homepage)

Lodging

The Inn at Penn
Sheraton Philadelphia University City Hotel
AKA at University City
The Study at University City

Flajolet Lectures

Wojciech Szpankowski (2020 Flajolet Lecture Prize Recipient)
Svante Janson (2022 Flajolet Lecture Prize Recipient)

Scope

Analysis of algorithms is a scientific basis for computation, providing a link between abstract algorithms and the performance characteristics of their implementations in the real world. The general effort to predict precisely the performance of algorithms has come to involve research in analytic combinatorics, the analysis of random discrete structures, asymptotic analysis, exact and limiting distributions, and other fields of inquiry in computer science, probability theory, and enumerative combinatorics. See http://aofa.cs.purdue.edu/

We invite papers in
We also welcome papers addressing problems such as: combinatorial algorithms, string searching and pattern matching, sublinear algorithms on massive data sets, network algorithms, graph algorithms, caching and memory hierarchies, indexing, data mining, data compression, coding and information theory, and computational finance. Papers are also welcome that address bridges to research in related fields such as statistical physics, computational biology, computational geometry, and simulation.

Keynote Speakers


Organization

Mark Daniel Ward, Organizer
Lida Ahmadi, Co-Organizer

Submissions

We invite you to submit an extended abstract (12 pages).

Click here for the Call for Papers

Program Committee

Luc Devroye
Amalia Duch
Cecilia Holmgren
Manuel Lladser
Cécile Mailler
Steve Melczer
Marni Mishna
Noela Müller
Ralph Neininger
Cyril Nicaud
Robin Pemantle
Carine Pivoteau
Mark Daniel Ward (chair)
Sebastian Wild

Steering Committee

Frédérique Bassino
Jim Fill
Clemens Heuberger
Hsien-Kuei Hwang
Ralph Neininger
Bruno Salvy, Chair

Conference Schedule (tentative)

All times are given in Eastern Daylight Time (same time as local time in Philadelphia, PA, USA)
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

Feedback?

Any additions, corrections, or other suggestions would be appreciated. Please contact mdw@purdue.edu

Last updated: Sunday, April 3, 2022