Strobl, Austria
June 8-12, 2015

Invited Speakers

Nicolas Broutin

Web page
Title: Universality of scaling limits of critical random graphs
Abstract

Over the last few years a wide array of random graph models have been postulated to understand properties of empirically observed networks. Most of these models come with a parameter $t$ (usually related to edge density) and a (model dependent) critical time $t_c$ which specifies when a giant component emerges. There is evidence to support that for a wide class of models, under moment conditions, the nature of this emergence is universal and looks like the classical Erdős-Rényi random graph, in that the extent of the range of the parameter in which phase transition occurs, but also of the sizes and structures of the large connected components within this range (when equipped with the graph distance) converge to random fractals related to Aldous' celebrated continuum random tree.

Our aim is to present and discuss a general program for proving such results. The results apply to a number of fundamental random graph models including the configuration model, inhomogeneous random graphs modulated via a finite kernel and bounded size rules.

Christina Goldschmidt

Web page
Title: A line-breaking construction of the stable trees
Abstract

Consider a Galton-Watson branching process with a critical offspring distribution, conditioned to have total progeny n. The family trees of such processes constitute a natural collection of models for random trees, which includes various standard combinatorial trees such as uniform random labelled trees and uniform binary planar trees. Since 1990, a beautiful theory of scaling limits for these objects has been developed. It turns out that there is a good way to rescale distances in the tree so that, in the limit as n tends to infinity, one obtains a compact limit object. The family of possible limiting objects, which are essentially "tree-like" path metric spaces, is now known as the stable trees. I will give a survey of some of this theory, and then talk about joint work with Bénédicte Haas (Paris-Dauphine), in which we give a new almost sure construction of the stable trees, via a surprisingly elementary line-breaking procedure.

Martin Dietzfelbinger

Web page
Title: Analysis of Quicksort with More than One Pivot
Abstract

Dual-pivot quicksort refers to variants of classical quicksort where in the partitioning step two pivots are used to split the input into three segments. This can be done in different ways, giving rise to different algorithms. Starting from 2009, a dual-pivot algorithm due to Yaroslavskiy received much attention, because it replaced the well-engineered quicksort algorithm in Oracle's Java 7 runtime library. Nebel and Wild (ESA 2012) analyzed this algorithm and showed that on average it uses $1.9 n \ln n + O(n)$ comparisons to sort an input of size n, beating standard quicksort, which uses $2 n \ln n + O(n)$ comparisons. We consider a model that captures all dual-pivot algorithms, give a unified analysis, and identify new dual-pivot algorithms that minimize the average number of key comparisons among all possible algorithms up to a linear term. This minimum is $1.8 n ln n + O(n)$. We also consider the generalized situation when there are $k > 2$ pivots. Kushagra et al. (ALENEX 2014) described one such algorithm. We can identify an abstract optimal algorithm for all k; the exact value of the optimal expected number of comparisons can so far be determined only for $k = 3$. It is $133/72 n \ln n \approx 1.705 n \ln n$.) We also comment on variants that choose pivots from a sample and other parameters like the number of data movements or cache faults that influence the empirical performance of a quicksort algorithm.

Elchanan Mossel

Web page
Title: The Surprising Power of Belief Propagation
Abstract

Belief Propagation is a very efficient and popular algorithm for inference.
While it is long known that the algorithm is exact for trees, its applicability for non-tree graphs have been intensively studied in coding theory, statistical physics and theoretical computer science for the last few decades. I will present the algorithm and some old and newer theoretical guarantees for its performance.

Markus Nebel

Web page
Title: Analytic Combinatorics in Biology
Abstract

At the latest with the computerization of many branches of their research discrete models became of increased importance to biologists. With the application of those models various quantitative questions were posed, most of which could be answered by methods from analytic combinatorics. Often, a special feature in this domain is the use of formal languages instead of directly applying the symbolic method. In this talk we will discuss some representative examples showing the elegance of the methods and also its enhancements in the context of biology.

Alois Panholzer

Web page
Title: Examples of two-parameter recurrences and their treatments
Abstract

Recurrences occur "almost everywhere" in the analysis of algorithms and random combinatorial structures. Whereas the (asymptotic) analysis of one-parameter recurrences is in many cases well-established by standard techniques or general theorems (as the "master theorem"), studies of two- (and more) parameter recurrences often remain "tricky". We give here some recent examples of, as we find, interesting problems during their treatments such recurrences pop up. In particular, we will comment on a detailed analysis of the so-called $(1+1)$-evolutionary algorithm (together with Hsien-Kuei Hwang, Nicolas Rolin, Tsung-Hsi Tsai and Wei-Mei Chen), on generalizations of parking functions for trees and mappings (together with Marie-Louise Bruner), and on the characterization of certain limiting distributions as Mixed Poisson distributions (together with Markus Kuba).

Carsten Schneider

Web page
Title: Symbolic Summation for Combinatorial and Related Problems
Abstract

Symbolic summation can be considered as one of the key technologies to solve combinatorial problems. In this talk I will work out the difference ring approach that supports the user to simplify multiple sums to expressions in terms of indefinite nested sums and products. In particular, I will illustrate how the summation algorithms of telescoping, creative telescoping and recurrence finding can be used to tackle combinatorial and related problems.

Lutz Warnke

Web page
Title: The phase transition in Achlioptas processes
Abstract

In the Erdős-Rényi random graph process, starting from an empty graph, in each step a new random edge is added to the evolving graph. One of its most interesting features is the 'percolation phase transition': as the ratio of the number of edges to vertices increases past a certain critical density, the global structure changes radically, from only small components to a single giant component plus small ones.

In this talk we consider Achlioptas processes, which have become a key example for random graph processes with dependencies between the edges. Starting from an empty graph these proceed as follows: in each step two potential edges are chosen uniformly at random, and using some rule one of them is selected and added to the evolving graph. We discuss why, for a large class of rules, the percolation phase transition is qualitatively comparable to the classical Erdős-Rényi process.

Based on joint work with Oliver Riordan.