TITLE: Is abelian group isomorphism in $\mathsf{AC^0}$?
QUESTION [8 upvotes]: An $O(n^2)$ running time algorithm for abelian group isomorphism is easy to see. Later working on this problem in 2003 Vikas improve the result from $O(n^2)$ running time  to $O(n \log n)$. In 2007, Kavitha showed that abelian group isomorphism can be done in linear time i.e. $O(n)$ time.
I know that abelian group isomorphism when groups are given by table representation is in $\mathsf{TC^0}$. Is there any research paper or article which shows that it is in $\mathsf{AC^0}$? I tried to google but get only the result that it is in $\mathsf{TC^0}$.

Question : Is abelian group isomorphism ( groups given in table representation ) in $\mathsf{AC^0}$

REPLY [4 votes]: Contrary to what is stated in the question, abelian group isomorphism is not known to be in $\mathrm{TC^0}$. Needless to say, this also means it is not known to be in $\mathrm{AC^0}$.
What is known is the following observation from [1]. Let $\mathrm{pow}$ denote the following problem: given a multiplication table of an abelian group $(A,{\cdot})$, elements $a,b\in A$, and $m$ in unary, determine if $b=a^m$. The structure theorem for finite abelian groups easily implies that if $A,B$ are two such groups of size $n$, then
$$\tag{$*$}A\simeq B\iff\forall m\le n\:\bigl|\{a\in A:a^m=1\}\bigr|=\bigl|\{b\in B:b^m=1\}\bigr|.$$
Since we can count polynomial-size sets in $\mathrm{TC^0}$, we obtain

Proposition 1: Abelian group isomorphism is computable in $\mathrm{TC^0(pow)}$.

Now, $\mathrm{pow}$ is clearly computable in L, and as shown in [2], also in the class FOLL. Thus,

Corollary 2: Abelian group isomorphism is computable in $\mathrm{L}$ and in $\mathrm{TC^0(FOLL)}$.

It is not known if $\mathrm{pow}$ is computable in $\mathrm{TC^0}$.
It seems that Corollary 2 is the best known result when it comes to the usual, “polynomial-size”, circuit classes. However, I observe that the problem is in the quasipolynomial version of $\mathrm{AC^0}$:

Proposition 3: Abelian group isomorphism is computable by a uniform sequence of quasipolynomial-size constant-depth Boolean circuits; more specifically, it is in $\Sigma_2\text-\mathrm{TIME}\bigl((\log n)^2\bigr)$.

(This translates into a uniform family of depth-3 circuits of size $2^{O((\log n)^2)}$, where the bottom disjunctions have fan-in only $O\bigl((\log n)^2\bigr)$; this is often called “depth $2\frac12$”.)
Proposition 3 is again a consequence of the structure theorem for finite abelian groups: any such group can be written as a direct sum of $O(\log n)$ cyclic subgroups, thus groups $A$ and $B$ are isomorphic iff they can be written as direct sums of cyclic subgroups with matching orders: that is, if $|A|=|B|=n$, then $A\simeq B$ iff

there exist

a sequence $\{m_i:i<k\}$ of $k\le\log n$ integers $m_i\le n$

sequences $\{a_i:i<k\}\subseteq A$ and $\{b_i:i<k\}\subseteq B$


such that

$\prod_{i<k}m_i=n$

$a_i^{m_i}=1$ and $b_i^{m_i}=1$ for each $i<k$

for all sequences $\{r_i:i<k\}$ of integers $0\le r_i<m_i$, not all zero:
$\prod_{i<k}a_i^{r_i}\ne1$ and $\prod_{i<k}b_i^{r_i}\ne 1$



The two main quantifiers are highlighted. To see that the stated bounds are not exceeded, we need to show that the identities $\prod_{i<k}a_i^{r_i}=1$ can be checked in $\mathrm{NTIME}\bigl((\log n)^2\bigr)$. This can be done by successively guessing and verifying values of the partial products $\prod_{i<l}a_i^{r_i}$ for $l=0,\dots,k$; moreover, for each $i$, we similarly guess and verify $O(\log r_i)$ partial results of the computation of $a_i^{r_i}$ by repeated squaring. In total, this makes $O\left(\sum_i\log r_i\right)\subseteq O\left(\sum_i\log m_i\right)\subseteq O(\log n)$ guesses, each of which takes $O(\log n)$ time to verify.
There is another way to prove Proposition 3: namely, note that in $(*)$, we only need to consider $m$ that are prime powers: $m=p^e$. In that case, the two offending sets that we need to count also have sizes that are powers of $p$; in particular, if they are unequal, they differ by a factor of at least $p$. Thus, it is enough to count the sizes of the two sets approximately. This can be done in quasipolynomial $\mathrm{AC^0}$ using Sipser’s coding lemma. And as I’ve already shown, $\mathrm{pow}$ can be computed in quasipolynomial $\mathrm{AC^0}$ by repeated squaring.
One consequence of Proposition 3 is that if the abelian isomorphism problem turns out not to be in $\mathrm{AC^0}$, this might be rather difficult to prove: in particular, one cannot just reduce PARITY or MAJORITY to the problem, as these require exponential-size bounded-depth circuits, not quasipolynomial. Even if we attempt to reduce PARITY on $m\ll n$ bits to the problem, there is not much room for the parameters: specifically, PARITY of super-polylogarithmically many bits is not computable by quasipolynomial-size constant-depth circuits, and PARITY of polylogarithmically many bits is already computable in $\mathrm{AC^0}$ by divide and conquer.
References:
[1] Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner: Graph isomorphism is not $\mathrm{AC^0}$-reducible to group isomorphism, ACM Transactions on Computation Theory 5 (2013), no. 4, article no. 13, doi: 10.1145/2540088.
[2] David Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie: On the complexity of some problems on groups input as multiplication tables, Journal of Computer and System Sciences 63 (2001), no. 2, pp. 186–200, doi: 10.1006/jcss.2001.1764.
{"set_name": "stack_exchange", "score": 8, "question_id": 40056}