<p>Contrary to what is stated in the question, abelian group isomorphism is <em>not</em> known to be in <span class="math-container">$\mathrm{TC^0}$</span>. Needless to say, this also means it is not known to be in <span class="math-container">$\mathrm{AC^0}$</span>.</p>
<p>What <em>is</em> known is the following observation from [1]. Let <span class="math-container">$\mathrm{pow}$</span> denote the following problem: given a multiplication table of an abelian group <span class="math-container">$(A,{\cdot})$</span>, elements <span class="math-container">$a,b\in A$</span>, and <span class="math-container">$m$</span> in unary, determine if <span class="math-container">$b=a^m$</span>. The structure theorem for finite abelian groups easily implies that if <span class="math-container">$A,B$</span> are two such groups of size <span class="math-container">$n$</span>, then</p>
<p><span class="math-container">$$\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|.$$</span></p>
<p>Since we can count polynomial-size sets in <span class="math-container">$\mathrm{TC^0}$</span>, we obtain</p>
<blockquote>
<p><strong>Proposition 1:</strong> Abelian group isomorphism is computable in <span class="math-container">$\mathrm{TC^0(pow)}$</span>.</p>
</blockquote>
<p>Now, <span class="math-container">$\mathrm{pow}$</span> is clearly computable in L, and as shown in [2], also in the class FOLL. Thus,</p>
<blockquote>
<p><strong>Corollary 2:</strong> Abelian group isomorphism is computable in <span class="math-container">$\mathrm{L}$</span> and in <span class="math-container">$\mathrm{TC^0(FOLL)}$</span>.</p>
</blockquote>
<p>It is not known if <span class="math-container">$\mathrm{pow}$</span> is computable in <span class="math-container">$\mathrm{TC^0}$</span>.</p>
<p>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 <em>quasipolynomial</em> version of <span class="math-container">$\mathrm{AC^0}$</span>:</p>
<blockquote>
<p><strong>Proposition 3:</strong> Abelian group isomorphism is computable by a uniform sequence of quasipolynomial-size constant-depth Boolean circuits; more specifically, it is in <span class="math-container">$\Sigma_2\text-\mathrm{TIME}\bigl((\log n)^2\bigr)$</span>.</p>
</blockquote>
<p>(This translates into a uniform family of depth-3 circuits of size <span class="math-container">$2^{O((\log n)^2)}$</span>, where the bottom disjunctions have fan-in only <span class="math-container">$O\bigl((\log n)^2\bigr)$</span>; this is often called “depth <span class="math-container">$2\frac12$</span>”.)</p>
<p>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 <span class="math-container">$O(\log n)$</span> cyclic subgroups, thus groups <span class="math-container">$A$</span> and <span class="math-container">$B$</span> are isomorphic iff they can be written as direct sums of cyclic subgroups with matching orders: that is, if <span class="math-container">$|A|=|B|=n$</span>, then <span class="math-container">$A\simeq B$</span> iff</p>
<blockquote>
<p><strong>there exist</strong></p>
<ul>
<li><p>a sequence <span class="math-container">$\{m_i:i&lt;k\}$</span> of <span class="math-container">$k\le\log n$</span> integers <span class="math-container">$m_i\le n$</span></p>
</li>
<li><p>sequences <span class="math-container">$\{a_i:i&lt;k\}\subseteq A$</span> and <span class="math-container">$\{b_i:i&lt;k\}\subseteq B$</span></p>
</li>
</ul>
<p>such that</p>
<ul>
<li><p><span class="math-container">$\prod_{i&lt;k}m_i=n$</span></p>
</li>
<li><p><span class="math-container">$a_i^{m_i}=1$</span> and <span class="math-container">$b_i^{m_i}=1$</span> for each <span class="math-container">$i&lt;k$</span></p>
</li>
<li><p><strong>for all</strong> sequences <span class="math-container">$\{r_i:i&lt;k\}$</span> of integers <span class="math-container">$0\le r_i&lt;m_i$</span>, not all zero:</p>
<p><span class="math-container">$\prod_{i&lt;k}a_i^{r_i}\ne1$</span> and <span class="math-container">$\prod_{i&lt;k}b_i^{r_i}\ne 1$</span></p>
</li>
</ul>
</blockquote>
<p>The two main quantifiers are highlighted. To see that the stated bounds are not exceeded, we need to show that the identities <span class="math-container">$\prod_{i&lt;k}a_i^{r_i}=1$</span> can be checked in <span class="math-container">$\mathrm{NTIME}\bigl((\log n)^2\bigr)$</span>. This can be done by successively guessing and verifying values of the partial products <span class="math-container">$\prod_{i&lt;l}a_i^{r_i}$</span> for <span class="math-container">$l=0,\dots,k$</span>; moreover, for each <span class="math-container">$i$</span>, we similarly guess and verify <span class="math-container">$O(\log r_i)$</span> partial results of the computation of <span class="math-container">$a_i^{r_i}$</span> by repeated squaring. In total, this makes <span class="math-container">$O\left(\sum_i\log r_i\right)\subseteq O\left(\sum_i\log m_i\right)\subseteq O(\log n)$</span> guesses, each of which takes <span class="math-container">$O(\log n)$</span> time to verify.</p>
<p>There is another way to prove Proposition 3: namely, note that in <span class="math-container">$(*)$</span>, we only need to consider <span class="math-container">$m$</span> that are prime powers: <span class="math-container">$m=p^e$</span>. In that case, the two offending sets that we need to count also have sizes that are powers of <span class="math-container">$p$</span>; in particular, if they are unequal, they differ by a factor of at least <span class="math-container">$p$</span>. Thus, it is enough to count the sizes of the two sets <em>approximately</em>. This can be done in quasipolynomial <span class="math-container">$\mathrm{AC^0}$</span> using Sipser’s coding lemma. And as I’ve already shown, <span class="math-container">$\mathrm{pow}$</span> can be computed in quasipolynomial <span class="math-container">$\mathrm{AC^0}$</span> by repeated squaring.</p>
<p>One consequence of Proposition 3 is that if the abelian isomorphism problem turns out not to be in <span class="math-container">$\mathrm{AC^0}$</span>, this might be rather difficult to prove: in particular, one cannot just reduce PARITY or MAJORITY to the problem, as these require <em>exponential-size</em> bounded-depth circuits, not quasipolynomial. Even if we attempt to reduce PARITY on <span class="math-container">$m\ll n$</span> 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 <span class="math-container">$\mathrm{AC^0}$</span> by divide and conquer.</p>
<p><strong>References:</strong></p>
<p>[1] Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner: <em>Graph isomorphism is not <span class="math-container">$\mathrm{AC^0}$</span>-reducible to group isomorphism</em>, ACM Transactions on Computation Theory 5 (2013), no. 4, article no. 13, doi: <a href="https://doi.org/10.1145/2540088" rel="noreferrer">10.1145/2540088</a>.</p>
<p>[2] David Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie: <em>On the complexity of some problems on groups input as multiplication tables</em>, Journal of Computer and System Sciences 63 (2001), no. 2, pp. 186–200, doi: <a href="https://doi.org/10.1006/jcss.2001.1764" rel="noreferrer">10.1006/jcss.2001.1764</a>.</p>

CC BY-SA 3.0
2018-02-05T21:14:03.233Z
Related (and very recent): https://arxiv.org/abs/1802.00659
Joshua Grochow
CC BY-SA 3.0
2018-02-05T18:23:18.457Z
2018-02-06T14:43:55.127Z
2020-06-17T09:38:08.363Z
Emil Jeřábek
<p>An $O(n^2)$ running time algorithm for abelian group isomorphism is easy to see. Later working on this problem in 2003 <a href="https://ac.els-cdn.com/S0022000096900458/1-s2.0-S0022000096900458-main.pdf?_tid=17524836-0407-11e8-8ed7-00000aacb35d&amp;acdnat=1517129094_5d411d1c0160944cbe14aaeb2545e0f7" rel="nofollow noreferrer">Vikas</a> improve the result from $O(n^2)$ running time  to $O(n \log n)$. In 2007, <a href="https://www.sciencedirect.com/science/article/pii/S0022000007000293" rel="nofollow noreferrer">Kavitha</a> showed that abelian group isomorphism can be done in linear time i.e. $O(n)$ time.</p>

<p>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}$.</p>

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

CC BY-SA 3.0
2018-01-28T09:59:02.773Z
question in cs, cs.stackexchange.com/questions/87369/is-finite-abelian-group-isomorphism-in-log-space - result shows abelian subgroup in $L$ and $TC^{0}(FOLL)$;
user3483902
CC BY-SA 3.0
2018-01-29T01:57:54.790Z
You already asked a similar question on CS.SE (https://cs.stackexchange.com/q/87369/755) and you already got an answer there that provides a citation to a paper that considers this problem.  Why didn't you mention that you had already gotten an answer and cite that paper?  Have you tried doing a literature search starting from that paper, to look for other papers that cite it or that it cites to see if there's anything in the literature on the subject?  You should be doing a literature search on your own before asking.... and you should be summarizing other answers you've already gotten.
D.W.
CC BY-SA 3.0
2018-01-29T05:19:32.743Z
@D.W See the question asked here is different as compare to what I have asked on https://cs.stackexchange.com/questions/87369/is-finite-abelian-group-isomorphism-in-log-space. I have done enough survey that's why I have mentioned few results above. Before commenting please read the full question. I have mentioned in the question that I know that problem is in $TC^0$.
new
CC BY-SA 3.0
2018-01-29T05:57:08.993Z
It would have been better to (a) cite the paper, and (b) do the literature search I suggest, and (c) report on the results of the literature search in the question.  You don't mention whether you did the literature search.  If you've done the literature search and haven't found anything, maybe it's not known.
D.W.
CC BY-SA 3.0
2018-01-29T11:08:06.787Z
Actually, a reference for the TC^0 claim would be nice.
Emil Jeřábek
CC BY-SA 3.0
2018-01-29T11:13:29.883Z
The problem is in the quasipolynomial version of AC^0 (with depth "2 and a half"). This follows from the fact that if you represent the multiplication tables by oracles, and give the size in binary as input, isomorphism can be tested in $\Sigma^P_2$ (roughly speaking, by guessing a sequence of generators of a direct decomposition into cyclic subgroups).
Emil Jeřábek
CC BY-SA 3.0
2018-01-29T21:34:58.377Z
After a brief search, I seriously doubt the TC^0 claim is correct. Even recent papers only cite the TC^0(FOLL) result as mentioned above.
Emil Jeřábek
CC BY-SA 3.0
2018-01-31T15:09:20.820Z
It is not known to be in TC0. Thus it is not known to be in AC0.
Jane
CC BY-SA 3.0
2018-01-31T17:20:40.220Z
@Jane Maybe it is known *not to be* in AC0 even if I doubt so, otherwise someone would have found the reference already (P vs NP argument style!). Or maybe it is not too hard to prove a lower bound and no one tried before?
holf
CC BY-SA 3.0
2018-01-31T18:14:33.903Z
@holf As I wrote, it *is* in the quasipolynomial version of AC^0. This might make it rather nontrivial to separate it from AC^0. In particular, you can't reduce PARITY (or a similar problem like MAJORITY) to it.
Emil Jeřábek
CC BY-SA 3.0
2018-02-01T12:15:45.037Z
It seems like between @Jane and Emil's last two comments, we essentially have as good an answer as we're likely to get. (Namely: not known to be in TC0, so not known to be in AC0; and, known to be in quasi-poly-size bounded-depth, so seemingly hard to separate from AC0.) Someone want to post?
Joshua Grochow
CC BY-SA 3.0
2018-02-05T18:23:51.377Z
@JoshuaGrochow OK, done.
Emil Jeřábek
<cc.complexity-theory><ds.algorithms>
Is abelian group isomorphism in $\mathsf{AC^0}$?
new
# Is abelian group isomorphism in $\mathsf{AC^0}$?

(Asked by: username_0 on 2018-01-28)

An $O(n^2)$ running time algorithm for abelian group isomorphism is easy to see. Later working on this problem in 2003 [Vikas](https://ac.els-cdn.com/S0022000096900458/1-s2.0-S0022000096900458-main.pdf?_tid=17524836-0407-11e8-8ed7-00000aacb35d&acdnat=1517129094_5d411d1c0160944cbe14aaeb2545e0f7) improve the result from $O(n^2)$ running time to $O(n \log n)$. In 2007, [Kavitha](https://www.sciencedirect.com/science/article/pii/S0022000007000293) 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}$

**Tags:** cc.complexity-theory, ds.algorithms
> **Comments:**
> **username_1**: question in cs, cs.stackexchange.com/questions/87369/is-finite-abelian-group-isomorphism-in-log-space - result shows abelian subgroup in $L$ and $TC^{0}(FOLL)$;  
> **username_2**: You already asked a similar question on CS.SE (https://cs.stackexchange.com/q/87369/755) and you already got an answer there that provides a citation to a paper that considers this problem.  Why didn't you mention that you had already gotten an answer and cite that paper?  Have you tried doing a literature search starting from that paper, to look for other papers that cite it or that it cites to see if there's anything in the literature on the subject?  You should be doing a literature search on your own before asking.... and you should be summarizing other answers you've already gotten.  
> **username_0**: @D.W See the question asked here is different as compare to what I have asked on https://cs.stackexchange.com/questions/87369/is-finite-abelian-group-isomorphism-in-log-space. I have done enough survey that's why I have mentioned few results above. Before commenting please read the full question. I have mentioned in the question that I know that problem is in $TC^0$.  
> **username_2**: It would have been better to (a) cite the paper, and (b) do the literature search I suggest, and (c) report on the results of the literature search in the question.  You don't mention whether you did the literature search.  If you've done the literature search and haven't found anything, maybe it's not known.  
> **username_3**: Actually, a reference for the TC^0 claim would be nice.  
> **username_3**: The problem is in the quasipolynomial version of AC^0 (with depth "2 and a half"). This follows from the fact that if you represent the multiplication tables by oracles, and give the size in binary as input, isomorphism can be tested in $\Sigma^P_2$ (roughly speaking, by guessing a sequence of generators of a direct decomposition into cyclic subgroups).  
> **username_3**: After a brief search, I seriously doubt the TC^0 claim is correct. Even recent papers only cite the TC^0(FOLL) result as mentioned above.  
> **username_4**: It is not known to be in TC0. Thus it is not known to be in AC0.  
> **username_5**: @Jane Maybe it is known *not to be* in AC0 even if I doubt so, otherwise someone would have found the reference already (P vs NP argument style!). Or maybe it is not too hard to prove a lower bound and no one tried before?  
> **username_3**: @holf As I wrote, it *is* in the quasipolynomial version of AC^0. This might make it rather nontrivial to separate it from AC^0. In particular, you can't reduce PARITY (or a similar problem like MAJORITY) to it.  
> **username_6**: It seems like between @Jane and Emil's last two comments, we essentially have as good an answer as we're likely to get. (Namely: not known to be in TC0, so not known to be in AC0; and, known to be in quasi-poly-size bounded-depth, so seemingly hard to separate from AC0.) Someone want to post?  
> **username_3**: @JoshuaGrochow OK, done.  

---

## 1 answers

### Answer by username_3 on 2018-02-05. Score: 4

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 of $k\le\log n$ integers $m\_i\le n$
> * sequences $\{a\_i:i and $\{b\_i:i
>
> such that
>
> * $\prod\_{i
> * $a\_i^{m\_i}=1$ and $b\_i^{m\_i}=1$ for each $i
> * **for all** sequences $\{r\_i:i of integers $0\le r\_i, not all zero:
>
>   $\prod\_{i and $\prod\_{i

The two main quantifiers are highlighted. To see that the stated bounds are not exceeded, we need to show that the identities $\prod\_{i 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 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](https://doi.org/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](https://doi.org/10.1006/jcss.2001.1764).

> **Comments:**
> **username_6**: Related (and very recent): https://arxiv.org/abs/1802.00659  

---

