  The rank of a finite algebraic structure with a single binary operation is
the minimum number of elements needed to express every other element under the
closure of the operation. In the case of groups, the previous best algorithm
for computing rank used polylogarithmic space. We reduce the best upper bounds
on the complexity of computing rank for groups and for quasigroups. This paper
proves that the rank problem for these algebraic structures can be verified by
highly restricted models of computation given only very short certificates of
correctness.
  Specifically, we prove that the problem of deciding whether the rank of a
finite quasigroup, given as a Cayley table, is smaller than a specified number
is decidable by a circuit of depth $O(\log \log n)$ augmented with $O(\log^2
n)$ nondeterministic bits. Furthermore, if the quasigroup is a group, then the
problem is also decidable by a Turing machine using $O(\log n)$ space and
$O(\log^2 n)$ bits of nondeterminism with the ability to read the
nondeterministic bits multiple times. Finally, we provide similar results for
related problems on other algebraic structures and other kinds of rank. These
new upper bounds are significant improvements, especially for groups. In
general, the lens of limited nondeterminism provides an easy way to improve
many simple algorithms, like the ones presented here, and we suspect it will be
especially useful for other algebraic algorithms.
