  Complexity rank for $C^*$-algebras was introduced by the second author and Yu
for applications towards the UCT: very roughly, this rank is at most $n$ if you
can repeatedly cut the $C^*$-algebra in half at most $n$ times, and end up with
something finite dimensional. In this paper, we study complexity rank, and also
a weak complexity rank that we introduce; having weak complexity rank at most
one can be thought of as `two-colored local finite-dimensionality'.
  We first show that for separable, unital, and simple $C^*$-algebras, weak
complexity rank one is equivalent to the conjunction of nuclear dimension one
and real rank zero. In particular, this shows that the UCT for all nuclear
$C^*$-algebras is equivalent to equality of the weak complexity rank and the
complexity ranks for Kirchberg algebras with zero $K$-theory groups. However,
we also show using a $K$-theoretic obstruction (torsion in $K_1$) that weak
complexity rank one and complexity rank one are not the same in general.
  We then use the Kirchberg-Phillips classification theorem to compute the
complexity rank of all UCT Kirchberg algebras: it is always one or two, with
the rank one case occurring if and only if the $K_1$-group is torsion free.
