We present several new provable algorithms for two variants of the code equivalence problem on linear error-correcting codes, the Linear Code Equivalence Problem (LCE) and the Permutation Code Equivalence Problem (PCE). Specifically, for arbitrary codes of block lengthnand dimensionkover any finite field Fq, we show: 1) A deterministic algorithm running in 2n+o(n+q)time for LCE. 2) A randomized algorithm running in 2n/2+o(n+q)time for LCE and PCE. 3) A quantum algorithm running in 2n/3+o(n+q)time for LCE and PCE. The second two algorithms improve on recent work of Nowakowski (PQCrypto 2025), which gave algorithms with similar running times but only for code equivalence onrandomcodes and only over fields of orderq≥ 7.

We present several new provable algorithms for two variants of the code equivalence problem on linear error-correcting codes, the Linear Code Equivalence Problem (LCE) and the Permutation Code Equivalence Problem (PCE). Specifically, for arbitrary codes of block length$n$and dimension$k$over any finite field$\mathbb{F}_{q}$, we show: 1)A deterministic algorithm running in$2^{n+o(n+q)}$time for LCE. 2)A randomized algorithm running in$2^{n / 2+o(n+q)}$time for LCE and PCE. 3)A quantum algorithm running in$2^{n / 3+o(n+q)}$time for LCE and PCE. The second two algorithms improve on recent work of Nowakowski (PQCrypto 2025), which gave algorithms with similar running times but only for code equivalence on random codes and only over fields of order$q \geq 7$.

An [n, k, d, r] Locally Recoverable Code (LRC) is a linear code of dimension k, length n, minimum distance d, and locality r, where the locality is the minimum number of coordinates of a codeword one has to access when recovering a single erasure. In this paper we construct a new family of optimal locally recoverable codes with availability t, i.e. any node has t distinct recovery sets. Our codes, for some sets of parameters, achieve the generalized Singleton bound for Locally Recoverable Codes, i.e. $d \leq n - k - \left\lceil {\frac{k}{r}} \right\rceil + 2$, while still allowing availability of nodes. From an information theoretical perspective, this is possible because the inequalities for the distance that take into account availability simply return the Singleton bound in certain regimes of parameters n, k, r, d, t, even with t ≥ 2. This allows the existence of codes with availability t ≥ 2 that still match the Singleton bound for LRCs mentioned earlier. Our construction relies on a new combinatorial structure, arising from the theory of finite fields, that allows to produce orthogonal partitions by leveraging the arithmetic of polynomial rings.