
Geometric inhomogeneous random graphs (GIRGs) are a model for scalefree
networks with underlying geometry. We study bootstrap percolation on these
graphs, which is a process modelling the spread of an infection of vertices
starting within a (small) local region. We show that the process exhibits a
phase transition in terms of the initial infection rate in this region. We
determine the speed of the process in the supercritical case, up to lower order
terms, and show that its evolution is fundamentally influenced by the
underlying geometry. For vertices with given position and expected degree, we
determine the infection time up to lower order terms. Finally, we show how this
knowledge can be used to contain the infection locally by removing relatively
few edges from the graph. This is the first time that the role of geometry on
bootstrap percolation is analysed mathematically for geometric scalefree
networks.

In ChungLu random graphs, a classic model for realworld networks, each
vertex is equipped with a weight drawn from a powerlaw distribution, and two
vertices form an edge independently with probability proportional to the
product of their weights. ChungLu graphs have average distance O(log log n)
and thus reproduce the smallworld phenomenon, a key property of realworld
networks. Modern, more realistic variants of this model also equip each vertex
with a random position in a specific underlying geometry. The edge probability
of two vertices then depends, say, inversely polynomial on their distance.
In this paper we study a generic augmented version of ChungLu random graphs.
We analyze a model where the edge probability of two vertices can depend
arbitrarily on their positions, as long as the marginal probability of forming
an edge (for two vertices with fixed weights, one fixed position, and one
random position) is as in ChungLu random graphs. The resulting class contains
ChungLu random graphs, hyperbolic random graphs, and geometric inhomogeneous
random graphs as special cases.
Our main result is that every random graph model in this general class has
the same average distance as ChungLu random graphs, up to a factor 1+o(1).
This shows in particular that specific choices, such as the underlying geometry
being Euclidean or the dependence on the distance being inversely polynomial,
do not significantly influence the average distance. The proof also yields that
our model has a giant component and polylogarithmic diameter with high
probability.

We study the Moran process as adapted by Lieberman, Hauert and Nowak. This is
a model of an evolving population on a graph or digraph where certain
individuals, called "mutants" have fitness r and other individuals, called
nonmutants have fitness 1. We focus on the situation where the mutation is
advantageous, in the sense that r>1. A family of digraphs is said to be
strongly amplifying if the extinction probability tends to 0 when the Moran
process is run on digraphs in this family. The mostamplifying known family of
digraphs is the family of megastars of Galanis et al. We show that this family
is optimal, up to logarithmic factors, since every stronglyconnected nvertex
digraph has extinction probability Omega(n^(1/2)). Next, we show that there is
an infinite family of undirected graphs, called dense incubators, whose
extinction probability is O(n^(1/3)). We show that this is optimal, up to
constant factors. Finally, we introduce sparse incubators, for varying edge
density, and show that the extinction probability of these graphs is O(n/m),
where m is the number of edges. Again, we show that this is optimal, up to
constant factors.

It is known that the evolutionary algorithm $(1+1)$EA with mutation rate
$c/n$ optimises every monotone function efficiently if $c<1$, and needs
exponential time on some monotone functions (HotTopic functions) if $c\geq
2.2$. We study the same question for a large variety of algorithms,
particularly for $(1+\lambda)$EA, $(\mu+1)$EA, $(\mu+1)$GA, their fast
counterparts like fast $(1+1)$EA, and for $(1+(\lambda,\lambda))$GA. We find
that all considered mutationbased algorithms show a similar dichotomy for
HotTopic functions, or even for all monotone functions. For the
$(1+(\lambda,\lambda))$GA, this dichotomy is in the parameter $c\gamma$, which
is the expected number of bit flips in an individual after mutation and
crossover, neglecting selection. For the fast algorithms, the dichotomy is in
$m_2/m_1$, where $m_1$ and $m_2$ are the first and second falling moment of the
number of bit flips. Surprisingly, the range of efficient parameters is not
affected by either population size $\mu$ nor by the offspring population size
$\lambda$.
The picture changes completely if crossover is allowed. The genetic
algorithms $(\mu+1)$GA and fast $(\mu+1)$GA are efficient for arbitrary
mutations strengths if $\mu$ is large enough.

We study sorting of permutations by random swaps if each comparison gives the
wrong result with some fixed probability $p<1/2$. We use this process as
prototype for the behaviour of randomized, comparisonbased optimization
heuristics in the presence of noisy comparisons. As quality measure, we compute
the expected fitness of the stationary distribution. To measure the runtime, we
compute the minimal number of steps after which the average fitness
approximates the expected fitness of the stationary distribution.
We study the process where in each round a random pair of elements at
distance at most $r$ are compared. We give theoretical results for the extreme
cases $r=1$ and $r=n$, and experimental results for the intermediate cases. We
find a tradeoff between faster convergence (for large $r$) and better quality
of the solution after convergence (for small $r$).

One of the easiest randomized greedy optimization algorithms is the following
evolutionary algorithm which aims at maximizing a boolean function $f:\{0,1\}^n
\to {\mathbb R}$. The algorithm starts with a random search point $\xi \in
\{0,1\}^n$, and in each round it flips each bit of $\xi$ with probability $c/n$
independently at random, where $c>0$ is a fixed constant. The thus created
offspring $\xi'$ replaces $\xi$ if and only if $f(\xi') \ge f(\xi)$. The
analysis of the runtime of this simple algorithm on monotone and on linear
functions turned out to be highly nontrivial. In this paper we review known
results and provide new and selfcontained proofs of partly stronger results.

We present a tight analysis for the wellstudied randomized 3majority
dynamics of stabilizing consensus, hence answering the main open question of
Becchetti et al. [SODA'16].
Consider a distributed system of n nodes, each initially holding an opinion
in {1, 2, ..., k}. The system should converge to a setting where all
(noncorrupted) nodes hold the same opinion. This consensus opinion should be
\emph{valid}, meaning that it should be among the initially supported opinions,
and the (fast) convergence should happen even in the presence of a malicious
adversary who can corrupt a bounded number of nodes per round and in particular
modify their opinions. A wellstudied distributed algorithm for this problem is
the 3majority dynamics, which works as follows: per round, each node gathers
three opinions  say by taking its own and two of other nodes sampled at
random  and then it sets its opinion equal to the majority of this set; ties
are broken arbitrarily, e.g., towards the node's own opinion.
Becchetti et al. [SODA'16] showed that the 3majority dynamics converges to
consensus in O((k^2\sqrt{\log n} + k\log n)(k+\log n)) rounds, even in the
presence of a limited adversary. We prove that, even with a stronger adversary,
the convergence happens within O(k\log n) rounds. This bound is known to be
optimal.

Realworld networks, like social networks or the internet infrastructure,
have structural properties such as large clustering coefficients that can best
be described in terms of an underlying geometry. This is why the focus of the
literature on theoretical models for realworld networks shifted from classic
models without geometry, such as ChungLu random graphs, to modern
geometrybased models, such as hyperbolic random graphs.
With this paper we contribute to the theoretical analysis of these modern,
more realistic random graph models. Instead of studying directly hyperbolic
random graphs, we use a generalization that we call geometric inhomogeneous
random graphs (GIRGs). Since we ignore constant factors in the edge
probabilities, GIRGs are technically simpler (specifically, we avoid hyperbolic
cosines), while preserving the qualitative behaviour of hyperbolic random
graphs, and we suggest to replace hyperbolic random graphs by this new model in
future theoretical studies.
We prove the following fundamental structural and algorithmic results on
GIRGs. (1) As our main contribution we provide a sampling algorithm that
generates a random graph from our model in expected linear time, improving the
bestknown sampling algorithm for hyperbolic random graphs by a substantial
factor O(n^0.5). (2) We establish that GIRGs have clustering coefficients in
{\Omega}(1), (3) we prove that GIRGs have small separators, i.e., it suffices
to delete a sublinear number of edges to break the giant component into two
large pieces, and (4) we show how to compress GIRGs using an expected linear
number of bits.

The algorithmic smallworld phenomenon, empirically established by Milgram's
letter forwarding experiments from the 60s, was theoretically explained by
Kleinberg in 2000. However, from today's perspective his model has several
severe shortcomings that limit the applicability to realworld networks. In
order to give a more convincing explanation of the algorithmic smallworld
phenomenon, we study decentralized greedy routing in a more flexible random
graph model (geometric inhomogeneous random graphs) which overcomes all
previous shortcomings. Apart from exhibiting good properties in theory, it has
also been extensively experimentally validated that this model reasonably
captures realworld networks.
In this model, the greedy routing protocol is purely distributed as each
vertex only needs to know information about its direct neighbors. We prove that
it succeeds with constant probability, and in case of success almost surely
finds an almost shortest path of length {\theta}(loglog n), where our bound is
tight including the leading constant. Moreover, we study natural local patching
methods which augment greedy routing by backtracking and which do not require
any global knowledge. We show that such methods can ensure success probability
1 in an asymptotically tight number of steps.
These results also address the question of Krioukov et al. whether there are
efficient local routing protocols for the internet graph. There were promising
experimental studies, but the question remained unsolved theoretically. Our
results give for the first time a rigorous and analytical affirmative answer.

One important goal of blackbox complexity theory is the development of
complexity models allowing to derive meaningful lower bounds for whole classes
of randomized search heuristics. Complementing classical runtime analysis,
blackbox models help us understand how algorithmic choices such as the
population size, the variation operators, or the selection rules influence the
optimization time. One example for such a result is the $\Omega(n \log n)$
lower bound for unary unbiased algorithms on functions with a unique global
optimum [Lehre/Witt, GECCO 2010], which tells us that higher arity operators or
biased sampling strategies are needed when trying to beat this bound. In lack
of analyzing techniques, almost no nontrivial bounds are known for other
restricted models. Proving such bounds therefore remains to be one of the main
challenges in blackbox complexity theory.
With this paper we contribute to our technical toolbox for lower bound
computations by proposing a new type of informationtheoretic argument. We
regard the permutation and bitinvariant version of \textsc{LeadingOnes} and
prove that its (1+1) elitist blackbox complexity is $\Omega(n^2)$, a bound
that is matched by (1+1)type evolutionary algorithms. The (1+1) elitist
complexity of \textsc{LeadingOnes} is thus considerably larger than its
unrestricted one, which is known to be of order $n\log\log n$ [Afshani et al.,
2013].

We study randomized algorithms for constrained optimization, in abstract
frameworks that include, in strictly increasing generality: convex programming;
LPtype problems; violator spaces; and a setting we introduce, consistent
spaces. Such algorithms typically involve a step of finding the optimal
solution for a random sample of the constraints. They exploit the condition
that, in finite dimension $\delta$, this sample optimum violates a provably
small expected fraction of the nonsampled constraints, with the fraction
decreasing in the sample size~$r$. We extend such algorithms by considering the
technique of removal, where a fixed number $k$ of constraints are removed from
the sample according to a fixed rule, with the goal of improving the solution
quality. This may have the effect of increasing the number of violated
nonsampled constraints. We study this increase, and bound it in a variety of
general settings. This work is motivated by, and extends, results on removal as
proposed for chanceconstrained optimization.
For many relevant values of $r$, $\delta$, and $k$, we prove matching upper
and lower bounds for the expected number of constraints violated by a random
sample, after the removal of $k$ constraints. For a large range of values of
$k$, the new upper bounds improve the previously best bounds for LPtype
problems, which moreover had only been known in special cases, and not in the
generality we consider. Moreover, we show that our results extend from finite
to infinite spaces, for chanceconstrained optimization.

Blackbox complexity studies lower bounds for the efficiency of
generalpurpose blackbox optimization algorithms such as evolutionary
algorithms and other search heuristics. Different models exist, each one being
designed to analyze a different aspect of typical heuristics such as the memory
size or the variation operators in use. While most of the previous works focus
on one particular such aspect, we consider in this work how the combination of
several algorithmic restrictions influence the blackbox complexity. Our
testbed are socalled OneMax functions, a classical set of test functions that
is intimately related to classic coinweighing problems and to the board game
Mastermind.
We analyze in particular the combined memoryrestricted rankingbased
blackbox complexity of OneMax for different memory sizes. While its isolated
memoryrestricted as well as its rankingbased blackbox complexity for bit
strings of length $n$ is only of order $n/\log n$, the combined model does not
allow for algorithms being faster than linear in $n$, as can be seen by
standard informationtheoretic considerations. We show that this linear bound
is indeed asymptotically tight. Similar results are obtained for other memory
and offspringsizes. Our results also apply to the (Monte Carlo) complexity of
OneMax in the recently introduced elitist model, in which only the bestsofar
solution can be kept in the memory. Finally, we also provide improved lower
bounds for the complexity of OneMax in the regarded models.
Our result enlivens the quest for natural evolutionary algorithms optimizing
OneMax in $o(n \log n)$ iterations.

Blackbox complexity theory provides lower bounds for the runtime of
blackbox optimizers like evolutionary algorithms and serves as an inspiration
for the design of new genetic algorithms. Several blackbox models covering
different classes of algorithms exist, each highlighting a different aspect of
the algorithms under considerations. In this work we add to the existing
blackbox notions a new \emph{elitist blackbox model}, in which algorithms are
required to base all decisions solely on (a fixed number of) the best search
points sampled so far. Our model combines features of the rankingbased and the
memoryrestricted blackbox models with elitist selection.
We provide several examples for which the elitist blackbox complexity is
exponentially larger than that the respective complexities in all previous
blackbox models, thus showing that the elitist blackbox complexity can be
much closer to the runtime of typical evolutionary algorithms.
We also introduce the concept of $p$Monte Carlo blackbox complexity, which
measures the time it takes to optimize a problem with failure probability at
most $p$. Even for small~$p$, the $p$Monte Carlo blackbox complexity of a
function class $\mathcal F$ can be smaller by an exponential factor than its
typically regarded Las Vegas complexity (which measures the \emph{expected}
time it takes to optimize $\mathcal F$).

Bootstrap percolation is a prominent framework for studying the spreading of
activity on a graph. We begin with an initial set of active vertices. The
process then proceeds in rounds, and further vertices become active as soon as
they have a certain number of active neighbors. A recurring feature in
bootstrap percolation theory is an `allornothing' phenomenon: either the size
of the starting set is so small that the process stops very soon, or it
percolates (almost) completely.
Motivated by several important phenomena observed in various types of
realworld networks we propose in this work a variant of bootstrap percolation
that exhibits a vastly different behavior. Our graphs have two types of
vertices: some of them obstruct the diffusion, while the others facilitate it.
We study the effect of this setting by analyzing the process on
Erd\H{o}sR\'enyi random graphs. Our main findings are twofold. First we show
that the presence of vertices hindering the diffusion does not result in a
stable behavior: tiny changes in the size of the starting set can dramatically
influence the size of the final active set. In particular, the process is
nonmonotone: a larger starting set can result in a smaller final set. In the
second part of the paper we show that this phenomenom arises from the
roundbased approach: if we move to a continuous time model in which every edge
draws its transmission time randomly, then we gain stability, and the process
stops with an active set that contains a nontrivial constant fraction of all
vertices. Moreover, we show that in the continuous time model percolation
occurs significantly faster compared to the classical roundbased model. Our
findings are in line with empirical observations and demonstrate the importance
of introducing various types of vertex behaviors in the mathematical model.

In an Achlioptas process, starting with a graph that has n vertices and no
edge, in each round $d \geq 1$ edges are drawn uniformly at random, and using
some rule exactly one of them is chosen and added to the evolving graph. For
the class of Achlioptas processes we investigate how much impact the rule has
on one of the most basic properties of a graph: connectivity. Our main results
are twofold. First, we study the prominent class of bounded size rules, which
select the edge to add according to the component sizes of its vertices,
treating all sizes larger than some constant equally. For such rules we provide
a fine analysis that exposes the limiting distribution of the number of rounds
until the graph gets connected, and we give a detailed picture of the dynamics
of the formation of the single component from smaller components. Second, our
results allow us to study the connectivity transition of all Achlioptas
processes, in the sense that we identify a process that accelerates it as much
as possible.

Blackbox complexity is a complexity theoretic measure for how difficult a
problem is to be optimized by a general purpose optimization algorithm. It is
thus one of the few means trying to understand which problems are tractable for
genetic algorithms and other randomized search heuristics.
Most previous work on blackbox complexity is on artificial test functions.
In this paper, we move a step forward and give a detailed analysis for the two
combinatorial problems minimum spanning tree and singlesource shortest paths.
Besides giving interesting bounds for their blackbox complexities, our work
reveals that the choice of how to model the optimization problem is nontrivial
here. This in particular comes true where the search space does not consist of
bit strings and where a reasonable definition of unbiasedness has to be agreed
on.

The CohenLenstra heuristic is a universal principle that assigns to each
group a probability that tells how often this group should occur "in nature".
The most important, but not the only, applications are sequences of class
groups, which behave like random sequences of groups with respect to the
socalled CohenLenstra probability measure.
So far, it was only possible to define this probability measure for finite
abelian $p$groups. We prove that it is also possible to define an analogous
probability measure on the set of \emph{all} finite abelian groups when
restricting to the $\Sigma$algebra on the set of all finite abelian groups
that is generated by uniform properties, thereby solving a problem that was
open since 1984.

In number theory, great efforts have been undertaken to study the
CohenLenstra probability measure on the set of all finite abelian $p$groups.
On the other hand, group theorists have studied a probability measure on the
set of all partitions induced by the probability that a randomly chosen
$n\times n$matrix over $\FF_p$ is contained in a conjucagy class associated
with this partitions, for $n \to \infty$.
This paper shows that both probability measures are identical. As a
consequence, a multitide of results can be transferred from each theory to the
other one. The paper contains a survey about the known methods to study the
probability measure and about the results that have been obtained so far, from
both communities.