@inproceedings{959f171e25fe49ae8b0b5d52bac07d9e,
title = "Black-box complexity: Breaking the O(n log n) barrier of leadingones",
abstract = "We show that the unrestricted black-box complexity of the n-dimensional XOR- and permutation-invariant LeadingOnes function class is O(n log(n) / loglogn). This shows that the recent natural looking O(nlogn) bound is not tight. The black-box optimization algorithm leading to this bound can be implemented in a way that only 3-ary unbiased variation operators are used. Hence our bound is also valid for the unbiased black-box complexity recently introduced by Lehre and Witt. The bound also remains valid if we impose the additional restriction that the black-box algorithm does not have access to the objective values but only to their relative order (ranking-based black-box complexity).",
keywords = "Algorithms, black-box complexity, query complexity, runtime analysis, theory",
author = "Benjamin Doerr and Carola Winzen",
year = "2012",
month = dec,
day = "14",
doi = "10.1007/978-3-642-35533-2\_18",
language = "English",
isbn = "9783642355325",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "205--216",
booktitle = "Artificial Evolution - 10th International Conference Evolution Artificielle, EA 2011, Revised Selected Papers",
note = "10th International Conference on Evolution Artificielle, EA 2011 ; Conference date: 24-10-2011 Through 26-10-2011",
}