  We show that the unrestricted black-box complexity of the $n$-dimensional
XOR- and permutation-invariant LeadingOnes function class is $O(n \log (n) /
\log \log n)$. This shows that the recent natural looking $O(n\log n)$ 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 (GECCO 2010). 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).
