# The (1+1) Elitist Black-Box Complexity of LeadingOnes

arXiv: https://arxiv.org/abs/1604.02355 · HTML: https://mlsanity.com/paper/1604.02355/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Apr 2016.

## Built on by (most cited first, 2 of 2)

- [Theory-inspired Parameter Control Benchmarks for Dynamic Algorithm Configuration](https://mlsanity.com/paper/2202.03259/) (2022)
- [Choosing the Right Algorithm With Hints From Complexity Theory](https://mlsanity.com/paper/2109.06584/) (2021)

## Abstract (arXiv)

One important goal of black-box 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, black-box 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 non-trivial bounds are known for other restricted models. Proving such bounds therefore remains to be one of the main challenges in black-box complexity theory. With this paper we contribute to our technical toolbox for lower bound computations by proposing a new type of information-theoretic argument. We regard the permutation- and bit-invariant version of textscLeadingOnes and prove that its (1+1) elitist black-box complexity is Omega(n2), a bound that is matched by (1+1)-type evolutionary algorithms. The (1+1) elitist complexity of textscLeadingOnes is thus considerably larger than its unrestricted one, which is known to be of order nloglog n [Afshani et al., 2013].