NP-hardness of minimum distance for cyclic codes

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A linear code $C\subseteq\mathbb F_q^n$ is cyclic if it is invariant under the coordinate rotation $(c_1,\ldots,c_n)\mapsto(c_n,c_1,\ldots,c_{n-1})$. It can be specified by a generator matrix. The Hamming weight $\operatorname{wt}(c)$ is the number of its nonzero coordinates, and its minimum distance is $d(C)=\min_{0\ne c\in C}\operatorname{wt}(c)$. The decision form, given a nonzero cyclic code and integer $w$, asks whether $d(C)\le w$.

Statement recorded in the supplied source.

Is the minimum-distance problem NP-hard when its input codes are restricted to cyclic codes? [S2]

Short English statement

Does restricting linear codes to cyclic codes preserve NP-hardness of computing their minimum distance?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 8800065 (AMR-087-0065). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Daniele Micciancio, Ideal Lattices: cryptographic applications and open problems, IPAM Number Theory and Cryptography: Open Problems workshop (9--13 October 2006), PDF page 35. https://helper.ipam.ucla.edu/publications/SCWS1/SCWS1_6240.pdf.