# AofA 2014

## Program

The conference will be held in Jussieu, in the premises of Université Pierre et Marie Curie. It will last five days, from June 16 to 20, 2014.

Abstracts of talks are available in the program below (just pass your mouse on the title to see the abstract). You can also download the pdf file of all abstracts here.

A compact view of the program as a one-page pdf file is available here.

### Monday, June 16

 08:30–09:00 Welcome 09:00–10:00 Donald Knuth Problems Philippe Would Have Liked (Flajolet Lecture) (slides) The speaker will discuss several intriguing problems that he believes are unsolved, and for which solutions may well open up new techniques of general importance for the analysis of algorithms. He cannot help but remember a lecture that David Hilbert once gave in Paris, although he warns the audience not to expect problems of Hilbertian quality. 10:00–10:30 Coffee Break 10:30–11:00 Axel Bacher and Andrea Sportiello Anticipated rejection algorithms and the Darling-Mandelbrot distribution. (slides) We study in limit law the complexity of some anticipated rejection random sampling algorithms. We express this complexity in terms of a probabilistic process, the threshold sum process. We show that, under the right conditions, the complexity is linear and admits as a limit law a so-called Darling--Mandelbrot distribution, studied by Darling (1952) and Lew (1994). We also give an explicit form to the density of the Darling--Mandelbrot distribution and derive some of its analytic properties. 11:00–11:30 James Zhao A Linear-Time Algorithm for Sampling Graphs with Given Degrees. (slides) We introduce a new algorithm for the asymptotically uniform sampling of graphs with given degrees, combining elements of combinatorial and Markov Chain Monte Carlo methods into a hybrid strategy. Under a typical sparseness condition, the runtime is linear in the number of edges, improving upon the previous best runtime by a factor equal to the maximum degree. We go on to show that this idea is applicable to a variety of other combinatorial families. 11:30–12:00 Markus E Nebel and Sebastian Wild. Pivot Sampling in Dual-Pivot Quicksort – Exploiting Asymmetries in Yaroslavskiy’s Partitioning Scheme (slides) The new dual-pivot Quicksort by Vladimir Yaroslavskiy, used in Oracle's Java runtime library since version 7, features intriguing asymmetries in its behavior. They were shown to cause a basic variant of this algorithm to use less comparisons than classic single-pivot Quicksort implementations. In this paper, we extend the analysis to the case where the two pivots are chosen as fixed order statistics of a random sample and give the precise leading term of the average number of comparisons, swaps and executed Java Bytecode instructions. It turns out that, unlike for classic Quicksort, where it is optimal to choose the pivot as median of the sample, the asymmetries in Yaroslavskiy's algorithm render pivots with a systematic skew more efficient than the symmetric choice. Moreover, the optimal skew heavily depends on the employed cost measure; most strikingly, abstract costs like the number of swaps and comparisons yield a very different result than counting Java Bytecode instructions, which can be assumed most closely related to actual running time. 12:00–14:00 Lunch 14:00–14:30 Svante Janson and Alfredo Viola A unified approach to linear probing hashing. (slides) We give a unified analysis of linear probing hashing with a general bucket size. We use both a combinatorial approach, giving exact formulas for generating functions, and a probabilistic approach, giving simple derivations of asymptotic results. Both approaches complement nicely, and give a good insight in the relation between linear probing and random walks. A key methodological contribution, at the core of Analytic Combinatorics, is the use of the symbolic method (based on $q$-calculus) to directly derive the generating functions to analyze. 14:30–15:00 Nicolas Broutin, Olivier Devillers and Ross Hemsley Efficiently Navigating a Random Delaunay Triangulation. (slides) Planar graph navigation is an important problem with significant implications to both point location in geometric data structures and routing in networks. Whilst many algorithms have been proposed, very little theoretical analysis is available for the properties of the paths generated or the computational resources required to generate them. In this work, we propose and analyse a new planar navigation algorithm for the Delaunay triangulation. We then demonstrate a number of strong theoretical guarantees for the algorithm when it is applied to a random set of points in a convex region. 15:00–15:30 Coffee Break 15:30–16:00 Vincent Pilaud and Juanjo Rué Analytic combinatorics of chord and hyperchord diagrams with k crossings. (slides) Using methods from Analytic Combinatorics, we study the families of perfect matchings, partitions, chord diagrams, and hyperchord diagrams on a disk with a prescribed number of crossings. For each family, we express the generating function of the configurations with exactly $k$ crossings as a rational function of the generating function of crossing-free configurations. Using these expressions, we study the singular behavior of these generating functions and derive asymptotic results on the counting sequences of the configurations with precisely $k$ crossings. Limiting distributions and random generators are also studied. 16:00–16:30 Antoine Genitrini, Bernhard Gittenberger and Cécile Mailler No Shannon effect induced by And/Or trees. (slides) Quantitative logic has been the subject of an increasing interest since a seminal paper by Chauvin et al. in 2004, which presented the first Analytic Combinatorics approach of the subject. Since then, the understanding of random Boolean trees has been deeply widened, even if the question of Shannon effect remains open for the majority of the models. We focus in this paper on the original case of Catalan \texttt{And/Or} trees and propose a new specification of those objects that implies easier ways to describe large families of trees. Equipped with this specification, we prove that the model of Catalan \texttt{And/Or} binary trees do not exhibit Shannon effect, i.e. there exists a family of functions with small complexities, that have a positive probability. 16:30–18:00 Poster Session (see here) 18:00– Cocktail

### Tuesday, June 17

 09:00–10:00 Colin McDiarmid Random graphs from a minor-closed class (Invited Talk) (slides) Consider a minor-closed class of graphs, such as the class of planar graphs. What can we say in general about typical graphs in the class? Can we learn things that could be useful for the design or analysis of algorithms? 10:00–10:30 Coffee Break 10:30–11:00 Mihyun Kang, Angelica Pachon and Pablo Rodriguez Connectivity for a modified binomial random graph by agglomeration. In the classical Erd\H os-R\'enyi random graph $G(n,p)$ there are $n$ vertices and each of the possible edges is independently present with probability $p$. One of the most known results for this model is the threshold for connectedness, a phenomenon which is tightly related to the nonexistence of isolated vertices. Numerous random graphs inspired in real networks are inhomogeneous in the sense that not all vertices have the same characteristic, which may influence the connection probability between pairs of vertices. The random graph $G(n,p)$ is homogeneous in this respect. Thus, with the aim to study real networks, new random graph models have been introduced and analyzed recently. The purpose of this paper is to contribute to this task by proposing a new inhomogeneous random graph model which is obtained in a constructive way from the classical Erd\H os-R\'enyi model. We consider an initial configuration of subsets of vertices and we call each subset a super-vertex, then the random graph model is defined by letting two super-vertices be connected if there is at least one edge between them in $G(n,p)$. Our main result concerns the threshold for connectedness. We point out that even though our model begins from $G(n,p)$, it assumes the existence of community structure and under certain conditions it exhibits a power law degree distribution, both important properties for real applications. 11:00–11:30 Abram Magner, Svante Janson, Giorgos Kollias and Wojciech Szpankowski On Symmetry of Uniform and Preferential Attachment Graphs. (slides) Motivated by the problem of graph structure compression under realistic source models, we study the symmetry behavior of preferential and uniform attachment graphs. These are two dynamic models of network growth in which new nodes attach to a constant number $m$ of existing ones according to some attachment scheme. We prove symmetry results for $m=1$ and $2$, and we conjecture that for $m\geq 3$, both models yield asymmetry with high probability. We provide new empirical evidence in terms of graph defect. We also prove that vertex defects in the uniform attachment model grow at most logarithmically with graph size, then use this to prove a weak asymmetry result for all values of $m$ in the uniform attachment model. Finally, we introduce a natural variation of the two models that incorporates preference of new nodes for nodes of a similar age, and we show that the change introduces symmetry for all values of $m$. 11:30–12:00 Pascal Maillard and Elliot Paquette Choices and Intervals. (slides) We consider a random interval splitting process, in which the splitting rule depends on the empirical distribution of interval lengths. We show that this empirical distribution converges to a limit almost surely as the number of intervals goes to infinity. We give a characterization of this limit as a solution of an ODE and use this to derive precise tail estimates. The convergence is established by showing that the size-biased empirical distribution evolves in the limit according to a certain deterministic evolution equation. Although this equation involves a non-local, non-linear operator, it can be studied thanks to a carefully chosen norm with respect to which this operator is contractive. In finite-dimensional settings, convergence results like this usually go under the name of \emph{stochastic approximation} and can be approached by a general method of Kushner and Clark. An important technical contribution of our work is the extension of this method to an infinite-dimensional setting. 12:00–14:00 Lunch 14:00–14:30 Katarzyna Grygiel and Pierre Lescanne Counting Terms in the Binary Lambda Calculus. (slides) In a paper entitled \emph{Binary lambda calculus and combinatory logic}, John Tromp presents a simple way of encoding lambda calculus terms as binary sequences. In what follows, we study the numbers of binary strings of a given size that represent lambda terms and derive results from their generating functions, especially that the number of terms of size $n$ grows roughly like $1.963447954\ldots^n$. 14:30–15:00 Daniel Krenn and Stephan Wagner The Number of Compositions into Powers of b. (slides) For a fixed integer base $b\geq2$, we consider the number of compositions of~$1$ into a given number of powers of~$b$ and, related, the maximum number of representations a positive integer can have as an ordered sum of powers of~$b$. We study the asymptotic growth of those numbers and give precise asymptotic formulae for them, thereby improving on earlier results of Molteni. Our approach uses generating functions, which we obtain from infinite transfer matrices. 15:00–15:30 Clemens Heuberger, Sara Kropf and Helmut Prodinger Asymptotic analysis of the sum of the output of transducers. (slides) As a generalization of the sum of digits function and other digital sequences, we asymptotically analyze sequences defined as the sum of the output of a transducer when reading a random integer in $[0, N)$. Analogues in higher dimensions are also considered. We show that sequences defined by a certain class of recursions can be written in this framework. Depending on properties of the transducer, we give the main term, the periodic fluctuation and an error term of the expected value and the variance of this sequence. In many cases, the periodic fluctuation of the expected value is continuous and nowhere differentiable. We give a general formula for the Fourier coefficients of this periodic function. Furthermore, the sequence is asymptotically normally distributed for many transducers. As an example, we analyze the abelian complexity function of the paperfolding sequence, which has recently been studied by Madill and Rampersad. 15:30–16:00 Coffee Break 16:00–16:30 Daniel Krenn, Dimbinaina Ralaivaosaona and Stephan Wagner On the Number of Multi-Base Representations of an Integer. (slides) In a multi-base representation of an integer (in contrast to, for example, the binary or decimal representation) the base (or radix) is replaced by products of powers of single bases. The resulting numeral system is usually redundant, which means that each integer can have multiple different digit expansions. We provide a general asymptotic formula for the number of such multi-base representations of a positive integer $n$. Moreover, we prove central limit theorems for the sum of digits and the Hamming weight of a random representation. 16:30–17:00 Philippe Jacquet Trie structure for Graph Sequences (slides) We present a data structure extending trie structure, that we call {\it graph tries} that allows to store label functions defined on a graph. In this paper we analyze the performance of such structure (size, insertion costs) for labels in acyclic regular graphs such as infinite trees and lattices. We analyze means and variance of this parameters. We also show an interesting theorem that establishes the equivalence between dePoissonization and analytic continuation of coefficients. 17:00–17:30 AofA business meeting 18:00–19:00 LIP6 Colloquium, Donald Knuth (see here)

### Wednesday, June 18

 09:00–10:00 Manuel Kauers Analysis of Summation Algorithms (Invited Talk) (slides) In the context of AofA, summation algorithms have so far mainly been of interest as a tool for solving summation problems arising in the complexity analysis of some other algorithm. But it is also interesting to analyze the complexity of summation algorithms themselves, and to estimate the sizes of their output. In the talk, we will give an overview over some recent results in this direction. 10:00–10:30 Coffee Break 10:30–11:00 Stephen Melczer and Marni Mishna Asymptotic lattice path enumeration using diagonals. (slides) This work considers restricted lattice path models in any dimension such that the defining step set is highly symmetric. Combining the kernel method with multivariate generating function analysis, we determine general formulas for the dominant asymptotics of counting sequences of walks restricted to the first orthant. The step sets under consideration are symmetric with respect to each axis, which is a strong condition, however the resulting formulas are very straightforward. The exponential growth of each model is given by the number of steps, while the sub-exponential growth depends only on the dimension of the underlying lattice and the number of steps moving forward in each coordinate. These expressions are derived by analyzing the singular variety of a multivariate rational function whose diagonal counts the lattice paths in question. 11:00–11:30 Olivier Bernardi, Gwendal Collet and Eric Fusy On the distance-profile of random rooted plane graphs. (slides) We study the distance-profile of the random rooted plane graph $G_n$ with $n$ edges (by a plane graph we mean a planar map with no loops nor multiple edges). Our main result is that the profile and radius of $G_n$ (with respect to the root-vertex), rescaled by $(2n)^{1/4}$, converge to explicit distributions related to the Brownian snake. A crucial ingredient of our proof is a bijection we have recently introduced between rooted outer-triangular plane graphs and rooted eulerian triangulations, combined with ingredients from Chassaing and Schaeffer (2004), Bousquet-M\'elou and Schaeffer (2000), and Addario-Berry and Albenque (2013). Our convergence result for plane graphs implies similar convergence results for random rooted loopless and general maps. 11:30–12:00 Cyril Banderier and Michael Wallner Some reflections on directed lattice paths. (slides) This article analyzes \emph{directed lattice paths}, when a boundary reflecting or absorbing condition is added to the classical models. The lattice paths are characterized by two time-independent sets of rules (also called steps) which have a privileged direction of increase and are therefore essentially one-dimensional objects. Depending on the spatial coordinate, one of the two sets of rules applies, namely one for altitude $0$ and one for altitude bigger than $0$. The abscissa $y=0$ thus acts as a border which either absorbs or reflects steps. The absorption model corresponds to the model analyzed by Banderier and Flajolet (Analytic combinatorics of directed lattice paths''), while the reflecting model leads to a more complicated situation. We show how the generating functions are then modified: the kernel method strikes again but here it unfortunately does not give a nice product formula. This makes the analysis more challenging, and, in the case of {\L}ukasiewicz walks, we give the asymptotics for the number of excursions, arches and meanders. Limit laws for the number of returns to 0 of excursions are given. We also compute the limit laws of the final altitude of meanders. The full analytic situation is more complicated than the Banderier--Flajolet model (partly because new critical compositions'' appear, forcing us to introduce new key quantities, like the drift at 0), and we quantify to what extent the global drift, and the drift at 0 play a r\^ole in the universal'' behavior of such walks.