Computers are typically described as deterministic machines that cannot make any random decisions. However, randomness is relevant for computer science in various forms. First, it can be used to make random decisions in an algorithm. Such randomized algorithms are often much simpler to implement and achieve good performance in the average case. Second, randomness can be a very useful tool in the analysis of (deterministic) algorithms. The resulting expected runtimes for real input distributions can be more meaningful for practical applications than general worst-case bounds.

This talk will present the use of randomness in a number of different domains. Starting from the very basics, it will discuss randomness in philosophy, quantum mechanics, mathematics, programming, social networks and optimization. No prior knowledge about randomness or any higher mathematics is needed to enjoy the talk.

The performance of large distributed systems crucially depends on effciently balancing their load. This has motivated a large amount of theoretical research how an imbalanced load vector can be smoothed with local algorithms. For technical reasons, the vast majority of previous work focuses on regular (or almost regular) graphs including symmetric topologies such as grids and hypercubes, and ignores the fact that large networks are often highly heterogenous.

We model large scale-free networks by Chung-Lu random graphs and analyze a simple local algorithm for iterative load balancing. On n-node graphs our distributed algorithm balances the load within O((log log n)²) steps. It does not need to know the exponent β∈(2,3) of the power-law degree distribution or the weights w_i of the graph model. To the best of our knowledge, this is the first result which shows that load-balancing can be done in double-logarithmic time on realistic graph classes.

Recently, Ant Colony Optimization (ACO) algorithms have been proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses focus on combinatorial problems, such as path finding.

We analyze an ACO algorithm in a setting where we try to optimize the simple OneMax test function, but with additive posterior noise sampled from a Gaussian distribution. Without noise the classical (µ + 1)-EA outperforms any ACO algorithm, with smaller µ being better; however, with large noise, the (µ + 1)-EA fails, even for high values of µ (which are known to help against small noise). We show that ACO is able to deal with arbitrarily large noise in a graceful manner, that is, as long as the evaporation factor ρ is small enough dependent on the parameter σ² of the noise and the dimension n of the search space, optimization will be successful.

Evolutionary algorithms use search operators like mutation, crossover and selection to "evolve" good solutions for optimisation problems. In the past decades there has been a long and controversial debate about when and why the crossover operator is useful. The building-block hypothesis assumes that crossover is particularly helpful if it can recombine good "building blocks", i. e. short parts of the genome that lead to high fitness. However, all attempts at proving this rigorously have been inconclusive. As of today, there is no rigorous and intuitive explanation for the usefulness of crossover. In this talk we provide such an explanation. For functions where "building blocks" need to be assembled, we prove rigorously that many evolutionary algorithms with crossover are twice as fast as the fastest evolutionary algorithm using only mutation. The reason is that crossover effectively turns fitness-neutral mutations into improvements by combining the right building blocks at a later stage. This also leads to surprising conclusions about the optimal mutation rate.

Large real-world networks are typically scale-free. Recent research has shown that such graphs are described best in a geometric space. More precisely, the internet can be mapped to a hyperbolic space such that geometric greedy routing performs close to optimal (Boguná, Papadopoulos, and Krioukov. Nature Communications, 1:62, 2010). This observation pushed the interest in hyperbolic networks as a natural model for scale-free networks. Hyperbolic random graphs follow a power-law degree distribution with controllable exponent and show high clustering (Gugelmann, Panagiotou, and Peter. ICALP, pp. 573-585, 2012).

For understanding the structure of the resulting graphs and for analyzing the behavior of network algorithms, the next question is bounding the size of the diameter. The only known bound is O((log n)^{32/((3-β)(5-β))})(Kiwi and Mitsche. ANALCO, pp. 26-39, 2015). We present two much simpler proofs for an improved upper bound of O((log n)^2/(3-β)) and a lower bound of Ω(log n). If the average degree is bounded from above by some constant, we show that the latter bound is tight by proving an upper bound of O(log n) for the diameter.

Imagine a network creation game where the peers of a fixed network can swap positions. Every peer has a set of friendships, i.e., a set of other peers to which it wants to minimize the distances. Different to previous research in this area, friendships are not assumed to be static, but the result of a dynamic process. This talk is about different such game variants discussing the effect of selfishness of the peers to convergence, convergence speed and the Price of Anarchy.

Recently, Ant Colony Optimization (ACO) algorithms have been proven to be efficient in uncertain environments, such as noisy or dynamically changing fitness functions. Most of these analyses focus on combinatorial problems, such as path finding.

We analyze an ACO algorithm in a setting where we try to optimize the simple OneMax test function, but with additive posterior noise sampled from a Gaussian distribution. Without noise the classical (µ + 1)-EA outperforms any ACO algorithm, with smaller µ being better; however, with large noise, the (µ + 1)-EA fails, even for high values of µ (which are known to help against small noise). We show that ACO is able to deal with arbitrarily large noise in a graceful manner, that is, as long as the evaporation factor ρ is small enough dependent on the parameter σ² of the noise and the dimension n of the search space, optimization will be successful.

Most research in the theory of evolutionary computation assumes that the problem at hand has a fixed problem size. This assumption does not always apply to real-world optimization challenges, where the length of an optimal solution may be unknown a priori. Following up on previous work of Cathabard, Lehre, and Yao [FOGA 2011] we analyze variants of the (1+1) evolutionary algorithm for problems with unknown solution length. For their setting, in which the solution length is sampled from a geometric distribution, we provide mutation rates that yield an expected optimization time that is of the same order as that of the (1+1) EA knowing the solution length. We then show that almost the same run times can be achieved even if no a priori information on the solution length is available. Finally, we provide mutation rates suitable for settings in which neither the solution length nor the positions of the relevant bits are known. Again we obtain almost optimal run times for the OneMax and LeadingOnes test functions, thus solving an open problem from Cathabard et al.

With this paper, we contribute to the theoretical understanding of randomized search heuristics by investigating their behavior on random 3-SAT instances. We improve the results for the (1+1) EA obtained by Sutton and Neumann [PPSN 2014, 942--951] in three ways. First, we reduce the upper bound by a linear factor and prove that the (1+1) EA obtains optimal solutions in time O(n log n) with high probability on asymptotically almost all high-density satisfiable 3-CNF formulas. Second, we extend the range of densities for which this bound holds to satisfiable formulas of at least logarithmic density. Finally, we complement these mathematical results with numerical experiments that summarize the behavior of the (1+1) EA on formulas along the density spectrum, and suggest that the implicit constants hidden in our bounds are low.

Our proofs are based on analyzing the run of the algorithm by establishing a fitness-distance correlation. This approach might be of independent interest and we are optimistic that it is useful for the analysis of randomized search heuristics in various other settings. To our knowledge, this is the first time that fitness-distance correlation is explicitly used to rigorously prove a performance statement for an evolutionary algorithm.

Using evolutionary algorithms to generate a diverse set of solutions where all of them meet a given quality criteria has gained increasing interest in recent years. In order to gain theoretical insights on the working principle of population-based evolutionary algorithms for this kind of diversity optimization, we have conducted a series of runtime analysis on the example problems OneMax, LeadingOnes and some classical vertex cover problems. We consider the case of complete bipartite graphs and paths and show how population-based evolutionary algorithms compute diverse sets of solutions where each solution meet the certain quality criteria defined according to the different problem. Currently we are working on applying diversity mechanism in some practical problems, such as TSP instance generation.

An overview of exceptionally good or simply interesting talks from this year's International Colloquium on Automata, Languages, and Programming in Kyoto, Japan.