5
$\begingroup$

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$

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

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), 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.)

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – Root
    Commented Feb 6, 2020 at 4:23
  • $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Commented Feb 6, 2020 at 4:57
  • $\begingroup$ If support splitting algorithm works for any random linear code than why isn't problem of code equivalence settled? At least for binary codes. $\endgroup$
    – Root
    Commented Feb 6, 2020 at 5:59
  • $\begingroup$ "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$." $\endgroup$
    – Joshua Grochow
    Commented Feb 6, 2020 at 6:05
  • 1
    $\begingroup$ 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? $\endgroup$
    – Root
    Commented Feb 13, 2020 at 16:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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