CS Paper Radar

Code Equivalence and Automorphism Problems for Codes

Jean-Francois Biasse, Alexandra V. Hostetler, Anuvrat Jaindungarwal

cs.CC ·submitted 2026-09-21 23:26 UTC · v2

Abstract

We study the complexity of the Code Equivalence problem and show that it is polynomially equivalent to several computational automorphism problems for codes. These problems ask for the cardinality (ACOUNT), an orbit partition (APART), and a generating set (AGEN) for the permutation automorphism group of a code. We present deterministic, polynomial-time reductions between Permutation Code Equivalence (PCE) and each of these problems, including a one-shot reduction from search-PCE to AGEN that makes a single oracle call. We present similar reductions between Linear Code Equivalence (LCE) and analogous problems for the monomial automorphism group of a code. All of our reductions work for any linear codes.

Closest papers

Nearest neighbours by meaning across the whole index.

Search-to-Decision Reductions for the Linear and General Code Equivalence Problems

cs.IT ·2026-08-11 ·Abhinaba Mazumder
similarity 0.83
Abstract

In this paper, we present efficient search-to-decision reductions for the Linear Code Equivalence (LCE) and Generalised Code Equivalence (GCE) problems. Our methodology is inspired by the recent search-to-decision reduction for Permutation Code Equivalence. We demonstrate how to recover the permutation component of the equivalence using a decision oracle, and subsequently show one way of recovering the diagonal and field automorphism components in deterministic polynomial time by leveraging the elegant Engel-Schneider algorithm for diagonal equivalence.

0.32

A search-to-decision reduction for the linear code equivalence problem

cs.CC ·2026-09-25 ·Jean-François Biasse, Giacomo Micheli, Benjamin Prada, Philip Waitkevich
theory similarity 0.76
Abstract

We present a polynomial-time reduction from the search variant of the linear code equivalence problem (i.e. the search for a linear isometry between the inputs) to its decisional variant. More precisely, given two linearly equivalent codes $\mathcal C_1,\mathcal C_2 \subseteq \mathbb{F}_q^n$, we show how to recover a linear isometry between them by making a polynomial number of queries to an oracle for decisional linear code equivalence. First, we prove that search-Permutation Code Equivalence (search-PCE -- the problem of finding a permutation $π\in\mathcal S_n$ mapping $\mathcal C_1$ to $\mathcal C_2$) reduces in polynomial time to PCE (i.e. the problem of deciding if there is a permutation map from $\mathcal C_1$ to $\mathcal C_2$) via at most $n^2$ oracle calls on instances of dimension $k$ and length at most $n^2(n+1)/2$. We then extend this approach to linearly equivalent codes: we recover the permutation part of a linear isometry via at most $n^2$ calls to a Linear Code Equivalence (LCE) oracle on instances of the same size, and we give a deterministic polynomial-time algorithm to recover the diagonal part once this permutation is known. Altogether, this yields a polynomial-time procedure to recover a linear isometry from an oracle for decisional LCE. From a linear-algebraic perspective, our results provide an explicit reconstruction of a monomial equivalence between two matrix representations from oracle access to the corresponding orbit membership problem.

0.37

On the lengths of MDS codes with a two-transitive permutation automorphism group

cs.IT math.COmath.GR ·2026-09-04 ·Haihua Deng, Tao Feng, Andrey V. Vasil'ev
similarity 0.63
Abstract · 16 pages, comments are welcome

Let $C$ be an $[n,k]_q$ maximum distance separable (MDS) code with $4\le k\le q-3$, and suppose that it has a $2$-transitive permutation automorphism group. In this paper we show that $n\le q+1$, so the MDS conjecture holds for this class of codes.

0.46

A Tutorial on Weight Structure of Polar Codes

cs.IT ·2026-08-19 ·Mohamamd Rowshan, Vlad-Florin Dragoi
published similarity 0.63
Abstract · This paper has been accepted by IEEE BITS: The Information Theory Magazine and will appear in the upcoming issue. 14 pages, 7 figures, 2 tab…

This tutorial introduces the algebraic foundations underlying the weight structure of polar codes. Using a monomial-based polynomial formalism, we explain how polar and Reed-Muller codes can be viewed as decreasing monomial codes, enabling systematic characterization and enumeration of low-weight codewords. Its goal is to provide an accessible introduction to affine automorphisms, orbit-based descriptions of minimum and low-weight codewords, and their role in weight enumeration. Through illustrative examples and high-level overviews of recursive and coset-based techniques, the paper aims to prepare readers for deeper engagement with the recent technical literature on the weight distribution of polar codes.

0.69

The 3/4 Conjecture for q-Ary Fix-Free Codes With at Most Three Distinct Codeword Lengths

cs.IT ·2026-09-16 ·Weiguo Gao, Zhi Shan
theory similarity 0.62
Abstract · 33 pages, 4 figures, 1 table

We prove the \(3/4\) conjecture for \(q\)-ary fix-free codes with at most three distinct codeword lengths, for every integer \(q\geq2\). Every prescribed length distribution with Kraft sum at most \(3/4\) is realized by a deterministic construction. We introduce a matrix approach based on an exact identity for the overlap between forbidden prefix extensions and suffix residuals. Natural numerical order fixes the shortest layer, and the remaining selection problem is expressed through row and column counts. A fixed-cardinality interpolation theorem supplies feasible sets of every intermediate cardinality between nested endpoints, provided their differences satisfy one-sided uniqueness and either acyclicity or integral slack. Reverse-order selection handles the uniform cases directly; in the remaining cases, layer completion and aligned groups provide endpoints for interpolation. Together, these methods extend the binary three-length result to arbitrary finite alphabets and give a deterministic procedure for constructing the code.

0.28

On the structure of polynomial ideal codes and additive Reed--Solomon codes

cs.IT ·2026-10-15 ·Umberto Martínez-Peñas, Rubén Rodríguez-Ballesteros
similarity 0.60
Abstract

We study structural properties of polynomial ideal (PI) codes and additive Reed--Solomon (aRS) codes in the folded Hamming metric (equivalently, the Hamming metric over a larger alphabet). We first determine the maximum possible length of PI codes, prove that the dual of every PI code is a generalized PI code, and deduce that PI codes are dually QMDS together with an explicit formula for their weight distribution. We then show that PI codes defined by irreducible polynomials correspond to aRS codes with pairwise nonconjugate evaluation points. For these aRS codes, the previous results on PI codes apply (duality, QMDS property and weight distribution). We show that, asymptotically, aRS codes with nonconjugate evaluation points achieve the same length as PI codes. We also compute the permutation group of such aRS codes. We also extend the family of PI codes to consider arbitrary polynomial modules (not necessarily pairwise coprime), and study when these and general aRS codes satisfy the QMDS and dually QMDS properties.

0.15

Low-Density Parity-Check Codes of High Girth from Permutation Polynomials

cs.IT ·2026-10-02 ·Tasawwar Hussain, Anthony Gómez-Fonseca, Tefjol Pllaha
similarity 0.60
Abstract · 6 pages, 1 figure

Quasi-cyclic low-density parity-check (QC-LDPC) codes are widely used in modern communication standards due to their simple structure and efficient encoder and decoder implementations. However, the commutativity of the circulant permutation matrices used in their construction significantly limits their girth and minimum distance, affecting iterative decoding performance. In this paper, we investigate protograph-based codes constructed using permutation polynomials of higher degree, focusing on a closed family of non-commuting binomial permutation polynomials that enables these constructions to exceed both of these girth and minimum distance upper bounds while maintaining a simple representation. Simulation results demonstrate improved decoding performance compared to constructions based on affine permutation polynomials, which include QC-LDPC codes.

0.15

Constructing Good Abelian Codes via Shift Bounds and Genetic Algorithms

cs.IT ·2026-08-19 ·Cong Yu, Hao Chen, Zhonghua Sun, Shixin Zhu
similarity 0.60
Abstract · 13 pages

This paper investigates the construction of linear codes via abelian codes over finite fields. By exploiting the algebraic structure of multivariate polynomial quotient rings, we derive lower bounds on the minimum distance using a generalized shift bound, which extends the classical van Lint-Wilson bound for cyclic codes. Several infinite families of abelian codes are explicitly constructed, including binary and ternary cases that extend previously known cyclic constructions. To find more abelian codes with good parameters, we apply a genetic algorithm that searches over defining sets represented as binary chromosomes of cyclotomic cosets; the fitness function compares the computed minimum distance against the best known linear code (BKLC) bounds. The search yields multiple record-breaking codes over F_3 and F_4, with improvements over Grassl's tables. Furthermore, the nested structure of these codes enables the application of Construction X, yielding additional linear codes with improved parameters. The results demonstrate that abelian codes, combined with heuristic search, form a viable way for discovering linear codes with unknown parameters.

0.28