Evolutionary algorithms (EAs) are optimization techniques inspired by nature. They are a popular choice if the problem at hand is, for example, noisy or highly complex and cannot be well formalized but the quality of a single solution can be easily measured. Typically, EAs maintain a set of samples from the solution space, which is iteratively updated, keeping better solutions and discarding bad ones. An alternative and more direct approach that is also commonly used is to not store samples but a probability distribution over the search space that generates these samples. Such algorithms are called estimation of distribution algorithms (EDAs).

In practice, EDAs are widely applied and perform very well. However, theoretical results on EDAs explaining this success are very scarce so far. We introduce an EDA framework we proposed, which subsumes many EDAs used for discrete domains, and we present our theoretical results for this framework. This includes robustness of EDAs to noise, restrictions on the way an EDA can update its distribution, and lower bounds of certain algorithms. We end by giving on outlook on how we want to extend our research.

Propositional satisfiability (SAT), the problem of deciding if a logical formula consisting of Boolean variables is satisfiable, is one of the most fundamental problems in computer science. Its worst-case hardness lies at the core of computational complexity theory, and the average-case analysis of SAT has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures.

Despite a long line of research and substantial progress, nearly all theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This motivates us to study non-uniform random k-SAT. In this model, a formula is formed by drawing m clauses independently at random, while in each clause k out of n variables are drawn independently at random without repetition according to some arbitrary probability distribution.

In the context of non-uniform random k-SAT, we study the satisfiability threshold, i.e., the number of randomly drawn clauses at which random formulas go from asymptotically almost surely satisfiable to asymptotically almost surely unsatisfiable. Such a threshold is called sharp if it approaches a step function as n increases.

We derive sufficient conditions on the variable-probability distribution for the threshold to be sharp. This work generalizes a result by Friedgut from 1999.

Greedy routing computes paths between nodes in a network by successively moving to the neighbor closest to the target with respect to coordinates given by an embedding into some metric space. Its advantage is that only local information is used for routing decisions. We present different algorithms for generating graph embeddings into the hyperbolic plane that are well suited for greedy routing. In particular our embeddings guarantee that greedy routing always succeeds in reaching the target and we try to minimize the lengths of the resulting greedy paths.

We evaluate our algorithms on multiple generated and real wold networks. For networks that are generally assumed to have a hidden underlying hyperbolic geometry, such as the Internet graph [1], we achieve near-optimal results, i.e., the resulting greedy paths are only slightly longer than the corresponding shortest paths. In the case of the Internet graph, they are only 6% longer when using our best algorithm, which greatly improves upon the previous best known embedding, whose creation required substantial manual intervention.

[1] Marián Boguná, Fragkiskos Papadopoulos, and Dmitri Krioukov. Sustaining the internet with hyperbolic mapping. Nature Communications, 1:62, 2010. doi:10.1038/ncomms1063

Drift Theory is currently the most common technique for the analysis of randomized search heuristics because of its broad applicability and the resulting tight first hitting time bounds. The biggest problem when applying a drift theorem is to find a suitable potential function which maps a complex space into a single number, capturing the essence of the state of the search in just one value.

In my presentation I would like to introduce you another method for the analysis of randomized search heuristics based on the Theory of Differential Equations. This method considers the deterministic counterpart of the randomized process by replacing probabilistic outcomes by their expectation, and then bounding the error with good probability.

Island models in evolutionary computation solve problems by a careful interplay of independently running evolutionary algorithms on the island and an exchange of good solutions between the islands. In this work, we conduct rigorous run time analyses for such island models trying to simultaneously obtain good run times and low communication effort.

This is joint work with Benjamin Doerr, Tobias Friedrich, Timo Kötzing, and Martin Schirneck.

We revisit the problem of optimizing a fitness function of unknown dimension; that is, we face a function defined over bit-strings of large length \(N\), but only \(n\ll N\) of them have an influence on the fitness. Neither the position of these relevant bits nor their number is known. In previous work, variants of the \((1+1)\) evolutionary algorithm (EA) have been developed that solve, for arbitrary \(s\in\mathbb{N}\), such OneMax and LeadingOnes instances, simultaneously for all \(n\in\mathbb{N}\), in expected time \(O(n (\log(n))^2 \log\log(n) \ldots \log^{(s-1)}(n) (\log^{(s)}(n))^{1+\varepsilon})\) and \(O(n^2 \log(n) \log\log(n) \ldots \log^{(s-1)}(n) (\log^{(s)}(n))^{1+\varepsilon})\), respectively; that is, in almost the same time as if \(n\) and the relevant bit positions were known.

In this work, we prove the first, almost matching, lower bounds for this setting. For LeadingOnes, we show that, for every \(s\in\mathbb{N}\), the \((1+1)\) EA with any mutation operator treating zeros and ones equally has an expected run time of \(\omega(n^2\log(n)\log\log(n)\ldots\log^{(s)}(n))\) when facing problem size \(n\). Aiming at closing the small remaining gap, we realize that, quite surprisingly, there is no asymptotically best performance. For any algorithm solving, for all \(n\), all instances of size \(n\) in expected time at most \(T(n)\), there is an algorithm doing the same in time \(T'(n)\) with \(T'=o(T)\). For OneMax we show results of similar flavor.

While many optimization problems work with a fixed number of decision variables and thus a fixed-length representation of possible solutions, genetic programming (GP) works on variable-length representations. A naturally occurring problem is that of bloat (unnecessary growth of solutions) slowing down optimization. Theoretical analyses could so far not bound bloat and required explicit assumptions on the magnitude of bloat.

In the paper "Bounding Bloat in Genetic Programming" we overcome previous assumptions on the magnitude of bloat and give matching or close-to-matching upper and lower bounds for the expected optimization time of two functions serving as examples.

The talk aims to provide an understanding of the setting we considered in the paper. Additionally, we will discuss the results in the context of previous results and conjectures and highlight the question whether bloat is as bad as it seems.

Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models.

We address this challenge by investigating a very recently introduced model by Goyal et al. [WINE'16] which focuses on robust networks in the presence of a strong adversary who attacks (and kills) nodes in the network and lets this attack spread virus-like to neighboring nodes and their neighbors. Our main result is to establish that this natural model is one of the few exceptions which are both realistic and computationally tractable. In particular, we answer an open question of Goyal et al. by providing an efficient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done efficiently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure and may thus be of independent interest.

Modern conflict-driven clause-learning (CDCL) Boolean SAT solvers routinely solve very large industrial SAT instances in relatively short periods of time. This phenomenon has stumped both theoreticians and practitioners since Boolean satisfiability is an NP-complete problem widely believed to be intractable. It is clear that these solvers somehow exploit the structure of real-world instances. However, to-date there have been few results that precisely characterize this structure or shed any light on why these SAT solvers are so efficient.

In this talk, I will present results that provide a deeper empirical understanding of why CDCL SAT solvers are so efficient, which may eventually lead to a complexity-theoretic result. Our results can be divided into two parts. First, I will talk about structural parameters that can characterize industrial instances and shed light on why they are easier to solve even though they may contain millions of variables. Second, I will talk about internals of CDCL SAT solvers, and describe why they are particularly suited to solve industrial instances.

In the context of black box optimization, the most common way to handle deceptive attractors is to periodically restart the algorithm. To derive the optimal restart time of a black-box algorithm, perfect knowledge of the convergence probability function is necessary. This quantity is often unknown or difficult to compute. In this paper, we show an intimate connection between the well-established theory of drift analysis and the study of optimal restart strategies. We demonstrate how to use this connection to derive useful estimates on the optimal restart time for elitist evolutionary algorithms, and we apply them to various fitness landscapes.

We first consider a simple, deception-free functions of unitation, and our method correctly recovers that no restart strategy yields improvement on the run time of two commonly studied local search algorithms. We then analyze two non-convex pseudo-Boolean functions on these algorithms, and show that the corresponding restart strategies are nontrivial. We conclude by studying an instance class of the NP-hard minimum vertex cover problem. We observe that a random local search may not find the minimum vertex cover in finitely many steps. We show that by using the optimal restart strategy it converges in polynomial time, and its expected run time is within a constant factor of the optimal run time in the absence of deception.

Propositional satisfiability (SAT) is one of the most fundamental problems in computer science. The worst-case hardness of SAT lies at the core of computational complexity theory. The average-case analysis of SAT has triggered the development of sophisticated rigorous and non-rigorous techniques for analyzing random structures.

Despite a long line of research and substantial progress, nearly all theoretical work on random SAT assumes a uniform distribution on the variables. In contrast, real-world instances often exhibit large fluctuations in variable occurrence. This can be modeled by a scale-free distribution of the variables, which results in distributions closer to industrial SAT instances.

We study random \(k\)-SAT on n variables, \(m=\Theta(n)\) clauses, and a power law distribution on the variable occurrences with exponent \(\beta\). We observe a satisfiability threshold at \(\beta=(2k−1)/(k−1)\). This threshold is tight in the sense that instances with \(\beta<(2k−1)/(k−1)−\varepsilon\) for any constant \(\varepsilon>0\) are unsatisfiable with high probability (w.h.p.). For \(\beta≥(2k−1)/(k−1)+\varepsilon\), the picture is reminiscent of the uniform case: instances are satisfiable w.h.p. for sufficiently small constant clause-variable ratios \(m/n\); they are unsatisfiable above a ratio \(m/n\) that depends on \(\beta\).

Network creation games investigate complex networks from a game-theoretic point of view. Based on the original model by Fabrikant et al. [PODC’03] many variants have been introduced. However, almost all versions have the drawback that edges are treated uniformly, i.e. every edge has the same cost and that this common parameter heavily influences the outcomes and the analysis of these games.

We propose and analyze simple and natural parameter-free network creation games with non-uniform edge cost. Our models are inspired by social networks where the cost of forming a link is proportional to the popularity of the targeted node. Besides results on the com- plexity of computing a best response and on various properties of the sequential versions, we show that the most general version of our model has constant Price of Anarchy. To the best of our knowledge, this is the first proof of a constant Price of Anarchy for any network creation game.

Inspired by real world examples, e.g. the Internet, researchers have introduced an abundance of strategic games to study natural phenomena in networks. Unfortunately, almost all of these games have the conceptual drawback of being computationally intractable, i.e. computing a best response strategy or checking if an equilibrium is reached is NP-hard. Thus, a main challenge in the field is to find tractable realistic network formation models.

We address this challenge by investigating a very recently introduced model by Goyal et al. [WINE'16] which focuses on robust networks in the presence of a strong adversary who attacks (and kills) nodes in the network and lets this attack spread virus-like to neighboring nodes and their neighbors. Our main result is to establish that this natural model is one of the few exceptions which are both realistic and computationally tractable. In particular, we answer an open question of Goyal et al. by providing an ecient algorithm for computing a best response strategy, which implies that deciding whether the game has reached a Nash equilibrium can be done eciently as well. Our algorithm essentially solves the problem of computing a minimal connection to a network which maximizes the reachability while hedging against severe attacks on the network infrastructure and may thus be of independent interest.

The road network graph of Europe contains more than 100 million nodes and half a billion edges. Performing route searches on such a graph in a setup with limited memory, like a Personal Navigation Device or a mobile phone, is a non-trivial task. For this purpose, modern maps are partitioned and stored in blocks (map tiles) according to a geometrical grid. Therefore, the major factor during the computation is the number of blocks of graph data loaded into memory. An A*-search algorithm with strong lower bounds for shortest path distances is important to optimize the number of cache loads.

Precomputed lower bounds for shortest paths between two tiles can be used to modify the order in which nodes are settled and further speed up Dijkstra-like searches. The right use of these properties will help to speed up route search on embedded devices and allow to build applications with a lower memory and energy footprint compared to the ones available today.

Automatic learners serve as models for learning in the limit from positive data with memory constraints. They trace back to Freivalds et al. (1995) who modelled Gold-style learning with memory restrictions in the recursion theoretic setting due to Blum and Blum (1995). The latter was transferred to automata theory by Jain et al. (2012). In contrast to the aforementioned classical setting, automatic learners accomodate the fact that the number of repetitions of words from the language to be learned may facilitate or impede the learning process thereof.

This talk extends a result by Jain et al. (2012) showing that the learnability of an automatic language class in the case that every word in the language is presented infinitely often to an automatic learner is equivalent to classical learnability. In addition to presenting results on automatic learning from presentations with finitely many repetitions, I am going to introduce the concept of automatic verification, link this to automatic learning and observe the influence of different repetition modi on the verifiability of automatic families.

This is joint work with Rupert Hölzl, Sanjay Jain, Philipp Schlicht and Frank Stephan.