Abstract The Generalized Hamming weights and their relative version, which generalize the minimum distance of a linear code, are relevant to numerous applications, including coding on the wire-tap channel of type II, t-resilient functions, bounding the cardinality of the output in list decoding algorithms, ramp secret sharing schemes, and quantum error correction. The generalized Hamming weights have been determined for some families of codes, including Cartesian codes and Hermitian one-point codes. In this paper, we determine the generalized Hamming weights of decreasing norm-trace codes, which are linear codes defined by evaluating sets of monomials that are closed under divisibility on the rational points of the extended norm-trace curve given by $$x^{u} = y^{q^{s - 1}} + y^{q^{s - 2}} + \cdots + y$$ x u = y q s - 1 + y q s - 2 + ⋯ + y over the finite field of cardinality $$q^s$$ q s , where u is a positive divisor of $$\frac{q^s - 1}{q - 1}$$ q s - 1 q - 1 . As a particular case, we obtain the weight hierarchy of one-point norm-trace codes and recover the result of Barbero and Munuera (2001) giving the weight hierarchy of one-point Hermitian codes. We also study the relative generalized Hamming weights for these codes and use them to construct impure quantum codes with excellent parameters.

Abstract Codes with locality, also known as locally recoverable codes, allow for recovery of erasures using proper subsets of other coordinates. These subsets are typically of small cardinality to promote recovery using limited network traffic and other resources. Hierarchical locally recoverable codes allow for recovery of erasures using sets of other symbols whose sizes increase as needed to allow for recovery of more symbols. In this paper, we describe a hierarchical recovery structure arising from geometry in Reed–Muller codes and codes with availability from fiber products of curves. We demonstrate how the fiber product hierarchical codes can be viewed as punctured subcodes of Reed–Muller codes, uniting the two constructions. This point of view provides natural structures for local recovery with availability at each level in the hierarchy.

In this paper, we consider using norm-trace codes over extension fields for error correction using partial information from received words. To do so, we define virtual projections of norm-trace codes and we implement a fractional decoding scheme. The scheme depends on a refined key equation tailored to the norm-trace code.

We extend coded distributed computing over finite fields to allow the number of workers to be larger than the field size. We give codes that work for fully general matrix multiplication and show that in this case we serendipitously have that all functions can be computed in a distributed fault-tolerant fashion over finite fields. This generalizes previous results on the topic. We prove that the associated codes achieve a recovery threshold similar to the ones for characteristic zero fields but now with a factor that is proportional to the genus of the underlying function field. In particular, we have that the recovery threshold of these codes is proportional to the classical complexity of matrix multiplication by a factor of at most the genus.

Abstract In this paper, we introduce curve-lifted codes over fields of arbitrary characteristic, inspired by Hermitian-lifted codes over $$\mathbb {F}_{2^r}$$ F 2 r . These codes are designed for locality and availability, and their particular parameters depend on the choice of curve and its properties. Due to the construction, the numbers of rational points of intersection between curves and lines play a key role. To demonstrate that and generate new families of locally recoverable codes (LRCs) with high availabilty, we focus on norm-trace-lifted codes.

Given two$q$-ary codes$C_{1}$and$C_{2}$, the relative hull of$C_{1}$with respect to$C_{2}$is the intersection$C_{1}\cap C_{2}^{\perp} $. We prove that when$q>2$, the relative hull dimension can be repeatedly reduced by one, down to a certain bound, by replacing either of the two codes with an equivalent one. The reduction of the relative hull dimension applies to hulls taken with respect to the$e$-Galois inner product, which has as special cases both the Euclidean and Hermitian inner products. We give conditions under which the relative hull dimension can be increased by one via equivalent codes when$q>2$. We study some consequences of the relative hull properties on entanglement-assisted quantum error-correcting codes and prove the existence of new entanglement-assisted quantum error-correcting maximum distance separable codes, meaning those whose parameters satisfy the quantum Singleton bound.

We consider the problem of secure distributed matrix multiplication (SDMM), where a user has two matrices and wishes to compute their product with the help of N honest but curious servers under the security constraint that any information about either A or B is not leaked to any server. This paper presents a new scheme that considers the inner product partition for matrices A and B. Our central technique relies on encoding matrices A and B in a Hermitian code and its dual code, respectively. We present the Hermitian Algebraic (HerA) scheme, which employs Hermitian codes and characterizes the partitioning and security capacities given entries of matrices belonging to a finite field with q2elements. We showcase that this scheme performs the secure distributed matrix multiplication in a significantly smaller finite field and expands security allowances compared to the existing results in the literature.

In this paper, we introduce multivariate Goppa codes, which contain, as a particular case, the well-known classical Goppa codes. We provide a parity check matrix for a multivariate Goppa code in terms of a tensor product of generalized Reed-Solomon codes. We prove that multivariate Goppa codes are subfield subcodes of augmented Cartesian codes. By showing how this new family of codes relates to a tensor product of generalized Reed-Solomon codes and augmented codes, we obtain information about the parameters, subcodes, duals, and hulls of multivariate Goppa codes. We see that in some instances, the hulls of multivariate Goppa codes (resp., tensor product of generalized Reed-Solomon codes) are also multivariate Goppa codes (resp. tensor product of generalized Reed-Solomon codes). We utilize the multivariate Goppa codes to obtain entanglement-assisted quantum error-correcting codes and to build families of long LCD, self-dual, or self-orthogonal codes.

In this paper, we consider approaches to designing Tanner codes to protect against symbol loss from multiple erasures. First, we note that Tanner codes inherit locality and availability from their inner codes, allowing one to design longer codes with specified locality and availability. Availability is desirable in that multiple disjoint repair groups increase the likelihood that symbols are available to repair erased ones. Even so, particular patterns of erasures well-distributed across the repair groups may prevent recovery. Hence, we consider an alternative using hierarchical locality which implements tiered recovery, where the tier utilized depends on the number of erasures. Finally, we define hierarchical stopping sets to characterize local message-passing decoder failure at the various repair levels.

In this paper, we introduce norm-trace-lifted codes over binary fields, which are codes with locality and high availability based on the norm-trace curve over the field ${\mathbb{F}_{{2^r}}}$. While they are inspired by Hermitian-lifted codes, norm-trace-lifted codes are easier to define and provide some potential advantages in terms of locality, meaning the number of symbols required to recover another, or alphabet size.

This paper presents secure MatDot codes, a family of evaluation codes that support secure distributed matrix multiplication via a careful selection of evaluation points that exploit the properties of the dual code. We show that the secure MatDot codes provide security against the user by using locally recoverable codes. These new codes complement the recently studied discrete Fourier transform codes for distributed matrix multiplication schemes that also provide security against the user. There are scenarios where the associated costs are the same for both families and instances where the secure MatDot codes offer a lower cost. In addition, the secure MatDot code provides an alternative way to handle the matrix multiplication by identifying the fastest servers in advance. In this way, it can determine a product using fewer servers, specified in advance, than the MatDot codes which achieve the optimal recovery threshold for distributed matrix multiplication schemes.

In this work, we present linear exact repair schemes for one or two erasures in decreasing monomial-Cartesian codes (DM-CC), a family of codes which provides a framework for polar codes. In the case of two erasures, the positions of the erasures should satisfy a certain restriction. We present families of augmented Reed-Muller (ARM) and augmented Cartesian codes (ACar) which are families of evaluation codes obtained by strategically adding vectors to Reed-Muller and Cartesian codes, respectively. We develop repair schemes for one or two erasures for these families of augmented codes. Unlike the repair scheme for two erasures of DM-CC, the repair scheme for two erasures for the augmented codes has no restrictions on the positions of the erasures. When the dimension and base field are fixed, we give examples where ARM and ACar codes provide a lower bandwidth (resp., bitwidth) in comparison with Reed-Solomon (resp., Hermitian) codes. When the length and base field are fixed, we give examples where ACar codes provide a lower bandwidth in comparison with ARM. Finally, we analyze the asymptotic behavior when the augmented codes achieve the maximum rate.

We present two families of augmented Reed-Muller (ARM) codes, which are evaluation codes obtained by adding specific vectors to a Reed-Muller code. We develop exact repair schemes for single erasures for these ARM codes. When a dimension and a base field are fixed, we give examples where ARM codes provide a lower bandwidth in comparison with Reed-Solomon codes. We analyze the asymptotical behavior when ARM codes achieve the maximum rate.

We present a new probabilistic decoding algorithm that can be used to perform fractional decoding of codes from the Hermitian curve. Fractional decoding means that the original codeword may be obtained from a received word using only an$\alpha$-proportion of symbols of the received word, provided not too many errors have occurred. The procedure presented makes use of fractional decoding of Reed-Solomon codes while allowing for the use of codes of similar lengths over smaller fields.

In this paper, we construct codes for local recovery of erasures with high availability and constant-bounded rate from the Hermitian curve. These new codes, called Hermitian-lifted codes, are evaluation codes with evaluation set being the set of $\mathbb{F}_{q^2}$-rational points on the affine curve. The novelty is in terms of the functions to be evaluated; they are a special set of monomials which restrict to low degree polynomials on lines intersected with the Hermitian curve. As a result, the positions corresponding to points on any line through a given point act as a recovery set for the position corresponding to that point.

In this article, we introduce a new family of polar codes from evaluation codes, called polar decreasing monomial-Cartesian codes, and prove that families of polar codes with multiple kernels over certain symmetric channels can be viewed as polar decreasing monomial-Cartesian codes. This offers a unified treatment for such codes over any finite field. We define decreasing monomial-Cartesian codes as evaluation codes obtained from a set of monomials closed under divisibility over a Cartesian product and determine their parameters (length, dimension, and minimum distance). We show that the dual of a decreasing monomial-Cartesian code is monomially equivalent to a decreasing monomial-Cartesian code. Polar decreasing monomial-Cartesian codes are then obtained by utilizing decreasing monomial-Cartesian codes whose sets of monomials are closed with respect to a partial order. We prove that any sequence of invertible matrices over an arbitrary field satisfying certain conditions polarizes any channel that is symmetric over the field.

We consider storage systems in which K files are stored over N nodes. A node may be systematic for a particular file in the sense that access to it gives access to the file. Alternatively, a node may be coded, meaning that it gives access to a particular file only when combined with other nodes (which may be coded or systematic). Requests for file fkarrive at rate λk, and we are interested in the rate that can be served by a particular system. In this paper, we determine the set of request arrival rates for the a 3-file coded storage system. We also provide an algorithm to maximize the rate of requests served for file K given λ1, . . . , λK-1in a general K-file case.

Combinatorial structures called stopping sets are useful in analyzing the performance of a linear code when coupled with an iterative decoding algorithm over an erasure channel. In this paper, we consider stopping sets of Hermitian codes.

This paper considers pseudocodewords of lowdensity parity-check codes over alphabets with prime cardinality p for use over the p-ary symmetric channel. Pseudocodewords are decoding algorithm outputs that may not be legitimate codewords. Here, we consider pseudocodewords arising from graph cover decoding and linear programming decoding. For codes over the binary alphabet, such pseudocodewords correspond to rational points of the fundamental polytope. They can be characterized via the fundamental cone, which is the conic hull of the fundamental polytope; the pseudocodewords are precisely those integer vectors within the fundamental cone that reduce modulo 2 to a codeword. In this paper, we determine a set of conditions that pseudocodewords of codes over Fp, the finite field of prime cardinality p, must satisfy. To do so, we introduce a class of critical multisets and a mapping, which associates a real number to each pseudocodeword over Fp. The real numbers associated with pseudocodewords are subject to lower bounds imposed by the critical multisets. The inequalities are given in terms of the parity-check matrix entries and critical multisets. This gives a necessary and sufficient condition for pseudocodewords of codes over F2and F3and a necessary condition for those over larger alphabets. In addition, irreducible pseudocodewords of codes over F3are found as a Hilbert basis for the lifted fundamental cone.

The performance of message-passing iterative decoding and linear programming decoding depends on the Tanner graph representation of the code. If the underlying graph contains cycles, then such algorithms could produce a noncodeword output. The study of pseudocodewords aims to explain this noncodeword output. We examine the structure of the pseudocodewords and show that there is a one-to-one correspondence between graph cover pseudocodewords and integer points in a lifted fundamental cone. This gives a simple proof that the generating function of the pseudocodewords for a general parity-check code is rational (a fact first proved by Li, Lu, and Wang (Lecture Notes in Computer Science, vol. 5557, 2009) via other methods). Our approach yields algorithms for producing this generating function and provides tools for studying the irreducible pseudocodewords. Specifically, Barvinok's algorithm and the Barvinok-Woods projection algorithm are applied, and irreducible pseudocodewords are found via a Hilbert basis for the lifted fundamental cone.

Algebraic geometry codes are defined by divisorsDandGon a curve over a finite field F. Often,Gis supported by a single F-rational point and the resulting code is called a one-point code. Recently, there has been interest in allowing the divisorGto be more general as this can result in superior codes. In particular, one may obtain a code with better parameters by allowingGto be supported bymdistinct F-rational points, wherem> 1. In this paper, we demonstrate that a multipoint algebraic geometry codeCmay be embedded in a one-point codeC'. Exploiting this fact, we obtain a minimum distance decoding algorithm for the multipoint codeC. This is accomplished via list decoding in the one-point code C'.

Abstract We consider a variant of the channel assignment problem in which frequencies are assigned to transmitters in a way that avoids interference while ensuring that all frequencies within the bandwidth are used. This is modeled as an L(2, 1)‐coloring of a graph which is no‐hole and irreducible in the sense that no color can be replaced with a smaller one. In this article, we show that if the network is any tree other than a star, then frequencies may be assigned in this fashion without increasing the bandwidth; that is, we show that for any such tree T, the inh‐span of T is equal to its span. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

In IEEE Transactions on Information Theory , vol. 48, no. 2, pp. 535-537, Feb. 2002, Xing and Chen show that there exist algebraic-geometry (AG) codes from the Hermitian function field over F/sub q//sup 2/ constructed using F/sub q//sup 2/-rational divisors which are improvements over the much-studied one-point Hermitian codes. In this correspondence, we construct such codes by using a place P of degree r > 1. This motivates a study of gap numbers and pole numbers at places of higher degree. In fact, the code parameters are estimated using the Weierstrass gap set of the place P and relating it to the gap set of the r-tuple of places of degree one lying over P in a constant field extension of degree r.

We construct algebraic geometry (AG) codes from the function field F(2/sup 2n+1/)(x,y)/F(2/sup 2n+1/) defined by y(2/sup 2n+1/)-y=(x(2/sup 2n+/)-x) where n is a positive integer. These codes are supported by two places, and many have parameters that are better than those of any comparable code supported by one place of the same function field. To define such codes, we determine and exploit the structure of the Weierstrass gap set of an arbitrary pair of rational places of F(2/sup 2n+1/)(x,y)/F(2/sup 2n+1/). Moreover, we find some codes over F/sub 8/ with parameters that are better than any known code.