More Like this

1. The weight hierarchy of decreasing norm-trace codes

   https://doi.org/10.1007/s10623-025-01619-7  

   Camps-Moreno, Eduardo; López, Hiram H; Matthews, Gretchen L; San-José, Rodrigo (April 2025, Designs, Codes and Cryptography)

   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}}+\cdots +y$over the finite field of cardinality$$q^s$$ $q^s$, whereuis a positive divisor of$$\frac{q^s - 1}{q - 1}$$ $\frac{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. 

   more » « less
2. Smoothing of Binary Codes, Uniform Distributions, and Applications

   https://doi.org/10.3390/e25111515  

   Pathegama, Madhura; Barg, Alexander (November 2023, Entropy)

   The action of a noise operator on a code transforms it into a distribution on the respective space. Some common examples from information theory include Bernoulli noise acting on a code in the Hamming space and Gaussian noise acting on a lattice in the Euclidean space. We aim to characterize the cases when the output distribution is close to the uniform distribution on the space, as measured by the Rényi divergence of order α∈(1,∞]. A version of this question is known as the channel resolvability problem in information theory, and it has implications for security guarantees in wiretap channels, error correction, discrepancy, worst-to-average case complexity reductions, and many other problems. Our work quantifies the requirements for asymptotic uniformity (perfect smoothing) and identifies explicit code families that achieve it under the action of the Bernoulli and ball noise operators on the code. We derive expressions for the minimum rate of codes required to attain asymptotically perfect smoothing. In proving our results, we leverage recent results from harmonic analysis of functions on the Hamming space. Another result pertains to the use of code families in Wyner’s transmission scheme on the binary wiretap channel. We identify explicit families that guarantee strong secrecy when applied in this scheme, showing that nested Reed–Muller codes can transmit messages reliably and securely over a binary symmetric wiretap channel with a positive rate. Finally, we establish a connection between smoothing and error correction in the binary symmetric channel. 

   more » « less
3. Input-output distance properties of good linear codes

   Roozbehani, Hajir; Polyanskiy, Yury (June 2018, 2018 IEEE Int. Symp. Inf. Theory (ISIT))

   —Consider a linear code defined as a mapping between vector spaces of dimensions k and n. Let β∗ denote the minimal (relative) weight among all images of input vectors of full Hamming weight k. Operationally, β∗ characterizes the threshold for adversarial (erasure) noise beyond which decoder is guaranteed to produce estimate of k-input with 100% symbol error rate (SER). This paper studies the relation between β∗ and δ, the minimum distance of the code, which gives the threshold for 0% SER. An optimal tradeoff between β∗ and δ is obtained (over large alphabets) and all linear codes achieving β∗ = 1 are classified: they are repetition-like. More generally, a design criteria is proposed for codes with favorable graceful degradation properties. As an example, it is shown that in an overdetermined system of n homogeneous linear equations in k variables (over a field) it is always possible to satisfy some k − 1 equations with non-zero assignments to every unknown, provided that any subset of k equations is linearly independent. This statement is true if and only if n ≥ 2k − 1. 

   more » « less
4. Code Sparsification and its Applications

   Khanna, Sanjeev; Putterman, Aaron Louie; Sudan, Madhu (January 2024, Society for Industrial and Applied Mathematics)

   We introduce a notion of code sparsification that generalizes the notion of cut sparsification in graphs. For a (linear) code C ⊆ 𝔽nq of dimension k a (1 ± ɛ)-sparsification of size s is given by a weighted set S ⊆ [n] with |S| ≤ s such that for every codeword c ∈ C the projection c|s of c to the set S has (weighted) hamming weight which is a (1 ± ɛ) approximation of the hamming weight of c. We show that for every code there exists a (1 ± ɛ)-sparsification of size s = Õ(k log(q)/ɛ2). This immediately implies known results on graph and hypergraph cut sparsification up to polylogarithmic factors (with a simple unified proof) — the former follows from the well-known fact that cuts in a graph form a linear code over 𝔽2, while the latter is obtained by a simple encoding of hypergraph cuts. Further, by connections between the eigenvalues of the Laplacians of Cayley graphs over to the weights of codewords, we also give the first proof of the existence of spectral Cayley graph sparsifiers over by Cayley graphs, i.e., where we sparsify the set of generators to nearly-optimal size. Additionally, this work can be viewed as a continuation of a line of works on building sparsifiers for constraint satisfaction problems (CSPs); this result shows that there exist near-linear size sparsifiers for CSPs over 𝔽p-valued variables whose unsatisfying assignments can be expressed as the zeros of a linear equation modulo a prime p. As an application we give a full characterization of ternary Boolean CSPs (CSPs where the underlying predicate acts on three Boolean variables) that allow for near-linear size sparsification. This makes progress on a question posed by Kogan and Krauthgamer (ITCS 2015) asking which CSPs allow for near-linear size sparsifiers (in the number of variables). At the heart of our result is a codeword counting bound that we believe is of independent interest. Indeed, extending Karger's cut-counting bound (SODA 1993), we show a novel decomposition theorem of linear codes: we show that every linear code has a (relatively) small subset of coordinates such that after deleting those coordinates, the code on the remaining coordinates has a smooth upper bound on the number of codewords of small weight. Using the deleted coordinates in addition to a (weighted) random sample of the remaining coordinates now allows us to sparsify the whole code. The proof of this decomposition theorem extends Karger's proof (and the contraction method) in a clean way, while enabling the extensions listed above without any additional complexity in the proofs. 

   more » « less
5. Code Sparsification and its Applications

   Khanna, Sanjeev; Putterman, Aaron Louie; Sudan, Madhu (January 2024, Society for Industrial and Applied Mathematics)

   We introduce a notion of code sparsification that generalizes the notion of cut sparsification in graphs. For a (linear) code C ⊆ 𝔽nq of dimension k a (1 ± ɛ)-sparsification of size s is given by a weighted set S ⊆ [n] with |S| ≤ s such that for every codeword c ∈ C the projection c|s of c to the set S has (weighted) hamming weight which is a (1 ± ɛ) approximation of the hamming weight of c. We show that for every code there exists a (1 ± ɛ)-sparsification of size s = Õ(k log(q)/ɛ2). This immediately implies known results on graph and hypergraph cut sparsification up to polylogarithmic factors (with a simple unified proof) — the former follows from the well-known fact that cuts in a graph form a linear code over 𝔽2, while the latter is obtained by a simple encoding of hypergraph cuts. Further, by connections between the eigenvalues of the Laplacians of Cayley graphs over to the weights of codewords, we also give the first proof of the existence of spectral Cayley graph sparsifiers over by Cayley graphs, i.e., where we sparsify the set of generators to nearly-optimal size. Additionally, this work can be viewed as a continuation of a line of works on building sparsifiers for constraint satisfaction problems (CSPs); this result shows that there exist near-linear size sparsifiers for CSPs over 𝔽p-valued variables whose unsatisfying assignments can be expressed as the zeros of a linear equation modulo a prime p. As an application we give a full characterization of ternary Boolean CSPs (CSPs where the underlying predicate acts on three Boolean variables) that allow for near-linear size sparsification. This makes progress on a question posed by Kogan and Krauthgamer (ITCS 2015) asking which CSPs allow for near-linear size sparsifiers (in the number of variables). At the heart of our result is a codeword counting bound that we believe is of independent interest. Indeed, extending Karger's cut-counting bound (SODA 1993), we show a novel decomposition theorem of linear codes: we show that every linear code has a (relatively) small subset of coordinates such that after deleting those coordinates, the code on the remaining coordinates has a smooth upper bound on the number of codewords of small weight. Using the deleted coordinates in addition to a (weighted) random sample of the remaining coordinates now allows us to sparsify the whole code. The proof of this decomposition theorem extends Karger's proof (and the contraction method) in a clean way, while enabling the extensions listed above without any additional complexity in the proofs. 

   more » « less