CS Paper Radar

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

Abhinaba Mazumder

cs.IT ·submitted 2026-08-11 14:29 UTC · v1

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Code Equivalence and Automorphism Problems for Codes

cs.CC ·2026-09-21 ·Jean-Francois Biasse, Alexandra V. Hostetler, Anuvrat Jaindungarwal
similarity 0.83
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.

0.38

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.78
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 Optimal Encodings and Systematicity in Function-Correcting Codes

cs.IT ·2026-10-06 ·Charul Rajput, Kanchana Lokshmii Jagatti, B. Sundar Rajan
theory similarity 0.57
Abstract

Function-correcting codes (FCCs) protect the value of a function $f$ of the message against $t$ errors. In the original formulation of Lenz et al. (2023), the encoding is systematic, and the lower bound of $2t$ on the redundancy relies on this form. Recently, D. Ho (arXiv, 2026) showed, for linear functions and linear encodings, that systematicity can cost redundancy. We begin with the OR function to show that the cost is not confined to the linear setting: a non-systematic encoding attains redundancy $1$ while every systematic encoding needs $2t$. For a linear function $f$ and a fixed linear code $C$, let $d_f$ denote the minimum distance between codewords of messages with different function values. Different generator matrices of $C$ assign different codewords to the messages and can give different values of $d_f$. We study which generator matrix of $C$ gives the largest $d_f$. We give an algorithm that constructs an optimal generator matrix and determines the optimal value as the weight of a codeword in a greedy basis of $C$. We then characterize, in terms of information sets, when a generator matrix in systematic form attains this optimum, and give a necessary condition that is checked on the low-weight codewords of $C$ alone. For two-valued functions, we drop both linearity and systematicity. Using the minimality of initial segments of the simplicial order with respect to Hamming neighbourhoods, we show that a non-systematic $(f,t)$-FCC of length $n$ exists if and only if a condition depending on $f$ only through the size of its smaller preimage holds. For $t=1$, redundancy $1$ is sufficient for every nonconstant two-valued function on $\mathbb{F}_2^k$ with $k\ge 10$. For general $t$, redundancy $1$ suffices for all two-valued functions once $k$ is large enough, and for each $s<2t$ we give an upper bound on the threshold in $k$ beyond which redundancy $s$ suffices.

0.15

Bilinear Hulls for Support Splitting: Characterization, Optimization, and Applications

cs.CR cs.IT ·2026-10-31 ·Yusuke Aikawa, Keita Ishizuka, Tomoki Moriya
publishedtheory similarity 0.56
Abstract · 25 pages. Accepted to SAC 2026; to appear in Lecture Notes in Computer Science (Springer). Author's accepted manuscript

Sendrier's Support Splitting Algorithm (SSA) is the standard solver for the Permutation Equivalence Problem (PEP); its cost is dominated by a term that grows exponentially in the hull dimension. We study, mathematically, how much this cost can be lowered by replacing the standard inner product, on which the hull is defined, with an alternative bilinear form. Two structural results give a complete answer: only a narrow two-parameter family of bilinear forms produces a hull on which SSA can still operate, namely those whose matrix in the standard basis is a linear combination of the identity and the all-ones matrix; and even within this family the hull dimension drops by at most one (with the reduction achieved on every self-dual code whose length is coprime to the field characteristic). Together, these results give a tight upper bound: since SSA on a code with hull dimension $h$ has cost dominated by $q^h$, replacing the standard hull with $\mathrm{Hull}_M$ lowers this dominant term from $q^h$ to at best $q^{h-1}$, so no bilinear-form generalization of the inner product can reduce the SSA cost by more than a factor of $q$, the field size. Going beyond this requires invariants outside the bilinear framework. As an application, we verify that PEP-based SPECK admits the factor-$q$ cost reduction, while LEP-based LESS and PKP-based PERK lie outside our framework. A SageMath implementation of the bilinear-hull preprocessing confirms feasibility at SPECK's recommended length $n = 252$.

0.71

Block basis reduction for linear codes in non-Hamming metrics

cs.IT cs.DM ·2026-10-19 ·N. S. Kolesnikov, S. A. Novoselov
similarity 0.54
Abstract

In this paper, we generalize the code basis reduction to non-Hamming metrics. We propose a block basis reduction (BKZ) algorithm for codes that works for all coordinate-additive metrics. Our algorithm is a generalization of the algorithm of Ghentiyala and Stephens-Davidowitz, which in turn is an adaptation of the famous BKZ algorithm for lattices to linear codes and the Hamming metric. For block size~$2$ (LLL), we propose a polynomial-time algorithm with complexity~$\mathcal{O}(n^4 q^3)$ operations in~$\mathbb{F}_q$, where~$n$ is the length of the code and~$q$ is the alphabet size. For the Lee metric we provide an implementation of our algorithms and present experimental results on finding low Lee weight codewords.

0.27

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.54
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

Worst-Case to Average-Case Reductions for Basic Linear Algebra

cs.DS cs.CC ·2026-11-02 ·Or Zamir
similarity 0.53
Abstract

We study worst-case to average-case reductions for basic linear-algebraic problems over finite fields. A seminal work of Blum, Luby, and Rubinfeld established that any algorithm that successfully multiplies more than $75\%$ of matrix pairs over any finite field, implies an algorithm with essentially the same running time multiplying any pair of matrices. A sequence of follow-ups reduced the needed fraction of successful input pairs to any positive constant. Despite most of the other basic linear algebraic operations being computationally equivalent to matrix multiplication in the worst case, no such worst-case to average-case reductions were known for them. Recently, Vaikuntanathan and Zamir introduced a cryptographic primitive called trapdoor matrices and used them to prove such worst-case to average-case reductions for matrix inversion, solving a linear system, and computing the determinant, all conditioned on common cryptographic assumptions. Our main result is the first unconditional time-preserving worst-case to average-case reduction for matrix inversion. Any algorithm that correctly inverts any constant positive fraction of uniformly random invertible matrices implies a worst-case such algorithm. We also significantly strengthen the conditional reductions based on trapdoored matrices: We establish reductions for deciding invertibility and computing rank at the optimal success thresholds, and qualitatively improve the success threshold needed in the reduction for determinant computation---while previous reductions all required the success probability to be at least $1/2$, we show that any fixed positive average-case success probability suffices for exact worst-case determinant computation over infinitely many finite fields.

0.30

Deterministic Shift Equivalence Testing for Sparse Polynomials

cs.DS cs.CC ·2026-10-19 ·Markus Bläser, Pranjal Dutta, Sagnik Dutta, Gorav Jindal
top venue similarity 0.53
Abstract · To appear in SODA 2027

We study the shift equivalence testing problem for high-degree sparse multivariate polynomials. Given explicit spar se representations of two polynomials $f,g\in\mathbb{Q}[x_1,\ldots,x_n]$, with exponents encoded in binary, sparsities $s$ and $t$, and total degree at most $d$, the task is to decide whether there is a vector $\mathbf{a}\in\mathbb{Q}^n$ such that $f(\mathbf{x}+\mathbf{a})\equiv g(\mathbf{x})$. Furthermore, one needs to output such a vector if it exists. Dvir, Oliveira, and Shpilka (ICALP 2014) studied shift equivalence for low-degree arithmetic circuits. Their framew ork does not apply directly to sparse polynomials, which are not closed under shifts, and they left open whether shift equivalence of sparse polynomials admits an efficient deterministic algorithm. We answer this question positively over $\mathbb{Q}$. If the input coefficients have bit-size at most $τ$, we sh ow that a rational shift of polynomial bit-size exists whenever the polynomials are shift equivalent. Moreover, our alg orithm outputs such a shift and has a running time of $\operatorname{poly}(n,s,t,τ,\log d)$ in the bit model. The ar ithmetic and structural parts of our result also hold over any field of characteristic zero or characteristic larger th an $d$.

0.37