7 papers
The -EA in Dynamic Environments
Georg Hasebe, Johannes Lengler, Raghu Raman Ravi
We study the -EA in dynamic linear environments, where in every generation selection is performed with respect to a freshly sampled linear function with positive weights.…
Improved Runtime Bound for the EA on BinVal
Joris Belder, Johannes Lengler, Raghu Raman Ravi
We study the EA on the Binary Value function BinVal. We show that it needs at most function evaluations to find the optimum when $μ= o(n/\log…
Runtime Analysis of the -ES in a Homogenous Progress Model
Johannes Lengler, Raghu Raman Ravi
We introduce a new simple model to study the fitness progress of Evolution Strategies (ES) in generic problems. In this model, we bypass the underlying fitness landscape and assume…
The Diameter of (Threshold) Geometric Inhomogeneous Random Graphs
Zylan Benjert, Kostas Lakis, Johannes Lengler +1
We prove that the diameter of threshold (zero temperature) Geometric Inhomogeneous Random Graphs (GIRG) is . This has strong implications for the runtime of many distri…
Adversarially-Robust Gossip Algorithms for Approximate Quantile and Mean Computations
Bernhard Haeupler, Marc Kaufmann, Raghu Raman Ravi +1
This paper presents gossip algorithms for aggregation tasks that demonstrate both robustness to adversarial corruptions of any order of magnitude and optimality across a substantia…
Rumour Spreading Depends on the Latent Geometry and Degree Distribution in Social Network Models
Marc Kaufmann, Kostas Lakis, Johannes Lengler +3
We study push-pull rumour spreading in ultra-small-world models for social networks where the degrees follow a power-law distribution. In a non-geometric setting, Fountoulakis, Pan…