<p>By taking direct sum of codes (given their two generator matrices <span class="math-container">$G_1, G_2$</span>, consider the block matrix <span class="math-container">$G_1 \oplus G_2 = \begin{bmatrix} G_1 &amp; 0 \\ 0 &amp; G_2 \end{bmatrix}$</span>), finding the automorphism group is at least as hard as testing isomorphism of codes (also called code equivalence). The current best upper bound for testing equivalence of linear codes is <span class="math-container">$2^{O(n)}$</span> (see <a href="http://dx.doi.org/10.1137/1.9781611973082.107" rel="noreferrer">Babai-Codenotti-G-Qiao, SODA '11</a>), and this algorithm can in fact give you generators for the automorphism group.</p>

<p>(For the above reduction I'm assuming that each code is indecomposable in the sense that neither code is itself a nontrivial direct sum, but I think this is true of (a) most/all codes people ever study and (b) most codes, ie a random code.)</p>

CC BY-SA 4.0
2020-02-06T04:23:39.520Z
any particular result on family of particular codes? In principal it could be possible to get a good complexity on codes that have some known properties like geometric structure for RS codes or algebraic structure for Quasi-cyclic etc. If I am getting things correctly, then this result is probably talking about complexity for a random code and not for a particular code family.
Root
CC BY-SA 4.0
2020-02-06T04:57:18.163Z
Actually, this result is for worst-case codes (ie all codes). I've seen it said (but having trouble finding the ref) that Sendrier's support-splitting algorithm works in poly time on random linear codes. I don't know about results for particular families.
Joshua Grochow
CC BY-SA 4.0
2020-02-06T05:59:36.793Z
If support splitting algorithm works for any random linear code than why isn't problem of code equivalence settled? At least for binary codes.
Root
CC BY-SA 4.0
2020-02-06T06:05:14.413Z
"Random" here is in a very specific technical sense, not in the colloquial sense of "arbitrary." The technical sense of "random" here means: "If you choose a code of length n purely at random (from some specified, natural distribution that's too long to write in this comment), the probability that the SSA works in poly(n) time is 1-f(n) where $\lim_{n \to \infty} f(n) = 0$."
Joshua Grochow
CC BY-SA 4.0
2020-02-06T06:25:51.077Z
Ok. If you can point out a reference that would be great. Thanks.
Root
CC BY-SA 4.0
2020-02-06T20:20:59.207Z
@Root: Here is Sendrier's original (I think) paper on SSA. I see the claim there in Section 7: https://hal.inria.fr/inria-00073037/document
Joshua Grochow
CC BY-SA 4.0
2020-02-13T16:46:52.317Z
I think reduction you provided in answer is classic one. Any standard reference I can cite for this? Also, if I understand reduction process correctly, it shows that if code automorphism for length $2n$ to equivalence over codes of length $n$ as a class. Clearly, it is sufficient for efficiency purposes. But what would be implications of showing statements like code equivalence for $G_{1},G_{2}$ can be solved then $aut(G_{1})$ can be found? That is instance to instance statement not class to class?
Root
CC BY-SA 4.0
2020-02-13T18:02:36.813Z
Indeed, this reduction is "essentially classical" in that it is basically the same one used to show that computing Aut(G) for G a graph is at least as hard as solving GI. Probly that can be found in Kobler-Schoning-Toran's book on GI (and they will probably have the original reference). The reduction in the other direction you ask for (if CodeEq can be solved, then one can find generators of Aut(G)) I believe is open, even instance-by-instance. The analogous statement for GI is known by coloring verts. Right now I don't see how to do it for codes (though it can basically be done for tensors).
Joshua Grochow
CC BY-SA 4.0
2020-02-13T18:28:30.037Z
In above reduction we show that for codes where G is $G_1 \oplus G_2$ aut finding is hard. It could potentially be possible that   if we consider class of codes where Generator matrix can not be written as direct sum of two Generator matrices and restrict our problem to such a class, the aut problem is strictly easier than code equivalence problem. Does that look correct?
Root
CC BY-SA 4.0
2020-02-14T04:50:12.570Z
I agree that what you say is possible in principle, but it feels a little unlikely to me. Probably there are some gadgets one can add to $G_1 \oplus G_2$ to make it into some $G'$ that isn't a direct sum, but still have the property that one can determine whether or not $G_1 \cong G_2$ from knowing $Aut(G')$. I'll try to think about this a bit more if I get some time.
Joshua Grochow
CC BY-SA 4.0
2020-02-05T18:56:42.873Z
2020-02-06T01:39:17.077Z
2020-02-06T01:39:17.077Z
Joshua Grochow
<p>What is the computational complexity (may be both classical or quantum) for finding automorphism group of a general linear code? 
Is there better bound on complexity if structure of code is known for eg. Reed Muller codes, goppa codes, quasi-cyclic codes, hadamard etc?</p>

<p>Here is reminder for definition of aut group for code generated by Generator matrix G</p>

<p><span class="math-container">$aut({G})= (A,P) :AGP=G$</span></p>

<cc.complexity-theory><quantum-computing><coding-theory>
Complexity of finding automorphism group of code
Root
# Complexity of finding automorphism group of code

(Asked by: username_0 on 2020-02-05)

What is the computational complexity (may be both classical or quantum) for finding automorphism group of a general linear code?
Is there better bound on complexity if structure of code is known for eg. Reed Muller codes, goppa codes, quasi-cyclic codes, hadamard etc?

Here is reminder for definition of aut group for code generated by Generator matrix G

$aut({G})= (A,P) :AGP=G$

**Tags:** cc.complexity-theory, quantum-computing, coding-theory

---

## 1 answers

### Answer by username_1 on 2020-02-05. Score: 7 | Accepted answer

By taking direct sum of codes (given their two generator matrices $G\_1, G\_2$, consider the block matrix $G\_1 \oplus G\_2 = \begin{bmatrix} G\_1 & 0 \\ 0 & G\_2 \end{bmatrix}$), finding the automorphism group is at least as hard as testing isomorphism of codes (also called code equivalence). The current best upper bound for testing equivalence of linear codes is $2^{O(n)}$ (see [Babai-Codenotti-G-Qiao, SODA '11](http://dx.doi.org/10.1137/1.9781611973082.107)), and this algorithm can in fact give you generators for the automorphism group.

(For the above reduction I'm assuming that each code is indecomposable in the sense that neither code is itself a nontrivial direct sum, but I think this is true of (a) most/all codes people ever study and (b) most codes, ie a random code.)

> **Comments:**
> **username_0**: any particular result on family of particular codes? In principal it could be possible to get a good complexity on codes that have some known properties like geometric structure for RS codes or algebraic structure for Quasi-cyclic etc. If I am getting things correctly, then this result is probably talking about complexity for a random code and not for a particular code family.  
> **username_1**: Actually, this result is for worst-case codes (ie all codes). I've seen it said (but having trouble finding the ref) that Sendrier's support-splitting algorithm works in poly time on random linear codes. I don't know about results for particular families.  
> **username_0**: If support splitting algorithm works for any random linear code than why isn't problem of code equivalence settled? At least for binary codes.  
> **username_1**: "Random" here is in a very specific technical sense, not in the colloquial sense of "arbitrary." The technical sense of "random" here means: "If you choose a code of length n purely at random (from some specified, natural distribution that's too long to write in this comment), the probability that the SSA works in poly(n) time is 1-f(n) where $\lim_{n \to \infty} f(n) = 0$."  
> **username_0**: Ok. If you can point out a reference that would be great. Thanks.  
> **username_1**: @Root: Here is Sendrier's original (I think) paper on SSA. I see the claim there in Section 7: https://hal.inria.fr/inria-00073037/document  
> **username_0**: I think reduction you provided in answer is classic one. Any standard reference I can cite for this? Also, if I understand reduction process correctly, it shows that if code automorphism for length $2n$ to equivalence over codes of length $n$ as a class. Clearly, it is sufficient for efficiency purposes. But what would be implications of showing statements like code equivalence for $G_{1},G_{2}$ can be solved then $aut(G_{1})$ can be found? That is instance to instance statement not class to class?  
> **username_1**: Indeed, this reduction is "essentially classical" in that it is basically the same one used to show that computing Aut(G) for G a graph is at least as hard as solving GI. Probly that can be found in Kobler-Schoning-Toran's book on GI (and they will probably have the original reference). The reduction in the other direction you ask for (if CodeEq can be solved, then one can find generators of Aut(G)) I believe is open, even instance-by-instance. The analogous statement for GI is known by coloring verts. Right now I don't see how to do it for codes (though it can basically be done for tensors).  
> **username_0**: In above reduction we show that for codes where G is $G_1 \oplus G_2$ aut finding is hard. It could potentially be possible that   if we consider class of codes where Generator matrix can not be written as direct sum of two Generator matrices and restrict our problem to such a class, the aut problem is strictly easier than code equivalence problem. Does that look correct?  
> **username_1**: I agree that what you say is possible in principle, but it feels a little unlikely to me. Probably there are some gadgets one can add to $G_1 \oplus G_2$ to make it into some $G'$ that isn't a direct sum, but still have the property that one can determine whether or not $G_1 \cong G_2$ from knowing $Aut(G')$. I'll try to think about this a bit more if I get some time.  

---

