In this paper, we describe an efficient search-to-decision reduction for the permutation code equivalence problem. Given two linear codes ${\mathcal{C}_1}$, ${\mathcal{C}_2}$ of length n and dimension k over ${\mathbb{F}_q}$, we describe an algorithm that finds $\pi \in {\mathcal{S}_n}$ such that $\pi \left( {{\mathcal{C}_1}} \right) = {\mathcal{C}_2}$ by using a polynomial number of queries to an oracle that decides whether two codes are permutation-equivalent.

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.

In this paper we construct new optimal hierarchical locally recoverable codes. Our construction is based on a combination of the ideas of Ballentine et al., (2019) and Sasidharan et al., (2015) with an algebraic number theoretical approach that allows to give a finer tuning of the minimum distance of the intermediate code (allowing larger dimension of the final code), and to remove restrictions on the arithmetic properties of$q$compared with the size of the locality sets in the hierarchy. In turn, we manage to obtain codes with a wider set of parameters both for the size$q$of the base field, and for the hierarchy size, while keeping the optimality of the codes we construct.

Let q be a prime power and Fqbe the finite field of size q. In this paper we provide a Galois theoretical framework that allows to produce good polynomials for the Tamo and Barg construction of optimal locally recoverable codes (LRC). Using our approach we construct new good polynomials and therefore optimal LRCs with new parameters. The existing theory of good polynomials fits entirely in our new framework. The key advantage of our method is that we do not need to rely on arithmetic properties of the pair (q, r), where r is the locality of the code.

In this paper we prove new lower bounds for the maximal size of permutation codes by connecting the theory of permutation codes with the theory of linear block codes. More specifically, using the columns of a parity check matrix of an [n,k,d]qlinear block code, we are able to prove the existence of a permutation code in the symmetric group of degree n, having minimum distance at least d and large cardinality. With our technique, we obtain new lower bounds for permutation codes that enhance the ones in the literature and provide asymptotic improvements in certain regimes of length and distance of the permutation code.

Let $n$ and $m$ be positive integers such that $n