Lifted Reed-Solomon and multiplicity codes are classes of codes, constructed from specific sets of$m$-variate polynomials. These codes allow for the design of high-rate codes that can recover every codeword or information symbol from many disjoint sets. Recently, the underlying approaches have been combined for the bi-variate case to construct lifted multiplicity codes, a generalization of lifted codes that can offer further rate improvements. We continue the study of these codes by first establishing new lower bounds on the rate of lifted Reed-Solomon codes for any number of variables$m$, which improve upon the known bounds for any$m\ge 4$. Next, we use these results to provide lower bounds on the rate and distance of lifted multiplicity codes obtained from polynomials in an arbitrary number of variables, which improve upon the known results for any$m\ge 3$. Specifically, we investigate a subcode of a lifted multiplicity code formed by the linear span of$m$-variate monomials whose restriction to an arbitrary line in${\mathbb {F}}_{q}^{m}$is equivalent to a low-degree univariate polynomial. We find the tight asymptotic behavior of the fraction of such monomials when the number of variables$m$is fixed and the alphabet size$q=2^\ell $is large. Using these results, we give a new explicit construction of batch codes utilizing lifted Reed-Solomon codes. For some parameter regimes, these codes have a better trade-off between parameters than previously known batch codes. Further, we show that lifted multiplicity codes have a better trade-off between redundancy and the number of disjoint recovering sets for every codeword or information symbol than previously known constructions, thereby providing the best known PIR codes for some parameter regimes. Additionally, we present a new local self-correction algorithm for lifted multiplicity codes.

Guo, Kopparty and Sudan have initiated the study of error-correcting codes derived by lifting of affine-invariant codes. Lifted Reed-Solomon (RS) codes are defined as the evaluation of polynomials in a vector space over a field by requiring their restriction to every line in the space to be a codeword of the RS code. In this paper, we investigate lifted RS codes and discuss their application to batch codes, a notion introduced in the context of private information retrieval and load-balancing in distributed storage systems. First, we improve the estimate of the code rate of lifted RS codes for lifting parameter m ≥ 3 and large field size. Second, a new explicit construction of batch codes utilizing lifted RS codes is proposed. For some parameter regimes, our codes have a better trade-off between parameters than previously known batch codes.

Lifted Reed-Solomon codes and multiplicity codes are two classes of evaluation codes that allow for the design of high-rate codes that can recover every codeword or information symbol from many disjoint sets. Recently, the underlying approaches have been combined to construct lifted bi-variate multiplicity codes, that can further improve on the rate. We continue the study of these codes by providing lower bounds on the rate and distance for lifted multiplicity codes obtained from polynomials in an arbitrary number of variables. Specifically, we investigate a subcode of a lifted multiplicity code formed by the linear span of m-variate monomials whose restriction to an arbitrary line in Fqmis equivalent to a low-degree uni-variate polynomial. We find the tight asymptotic behavior of the fraction of such monomials when the number of variables m is fixed and the alphabet sizeq=2ℓis large. For some parameter regimes, lifted multiplicity codes are then shown to have a better tradeoff between redundancy and the number of disjoint recovering sets for every codeword or information symbol than previously known constructions.

In this paper, we derive the exact weight distributions that emerge during each stage of successive cancellation decoding of polar codes. Though we do not compute the distance spectrum of polar codes, the results allow us to get an estimate of the decoding error probability and to show a link between the first nonzero components of the weight distribution and the partial order between the synthetic channels. Also, we establish the minimal distance between two cosets associated with two paths that differ in two positions. This can be regarded as a first step toward analyzing the weight distributions for successive cancellation list decoding.

A primitive k-batch code encodes a string x of length n into a stringy of length N, such that each multiset of k symbols from x has k mutually disjoint recovering sets from y. In this paper, we discuss new constructions of binary primitive batch codes. First, we develop novel explicit and random coding constructions of linear primitive batch codes based on finite geometries. Second, a new explicit coding construction of binary primitive batch codes based on bivariate lifted multiplicity codes is provided. For any k = nεwith ε ∈ (0, 0.47) \ {1/5, 1/4}, our proposed codes have a better trade-off between the redundancy and the parameters k, n than previously known batch codes.