Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Computing rank of finite algebraic structures with limited
  nondeterminism   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.

10
The categories of this paper are: q-bio
35
The categories of this paper are: mtrl-th
0
The categories of this paper are: hep-ph
13
The categories of this paper are: quant-ph
15
The categories of this paper are: nucl-ex
4
The categories of this paper are: cond-mat
26
The categories of this paper are: bayes-an
31
The categories of this paper are: ao-sci
16
The categories of this paper are: stat
11
The categories of this paper are: hep-lat
9
The categories of this paper are: nlin
36
The categories of this paper are: cmp-lg
25
The categories of this paper are: patt-sol
23
The categories of this paper are: solv-int
3
The categories of this paper are: physics
28
The categories of this paper are: alg-geom