8
$\begingroup$

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}$

$\endgroup$
  • 3
    $\begingroup$ 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)$; $\endgroup$ – user3483902 Jan 28 '18 at 9:59
  • 4
    $\begingroup$ You already asked a similar question on CS.SE (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. $\endgroup$ – D.W. Jan 29 '18 at 1:57
  • 3
    $\begingroup$ 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. $\endgroup$ – D.W. Jan 29 '18 at 5:57
  • 3
    $\begingroup$ Actually, a reference for the TC^0 claim would be nice. $\endgroup$ – Emil Jeřábek Jan 29 '18 at 11:08
  • 3
    $\begingroup$ It is not known to be in TC0. Thus it is not known to be in AC0. $\endgroup$ – Jane Jan 31 '18 at 15:09
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.