Linear programming bounds for codes via a covering argument
From MaRDI portal
Abstract: We recover the first linear programming bound of McEliece, Rodemich, Rumsey, and Welch for binary error-correcting codes and designs via a covering argument. It is possible to show, interpreting the following notions appropriately, that if a code has a large distance, then its dual has a small covering radius and, therefore, is large. This implies the original code to be small. We also point out (in conjunction with further work) that this bound is a natural isoperimetric constant of the Hamming cube, related to its Faber-Krahn minima. While our approach belongs to the general framework of Delsarte's linear programming method, its main technical ingredient is Fourier duality for the Hamming cube. In particular, we do not deal directly with Delsarte's linear program or orthogonal polynomial theory.
Recommendations
Cites work
- A fast and simple randomized parallel algorithm for the maximal independent set problem
- An upper bound on the covering radius as a function of the dual distance
- Generalized Alon--Boppana Theorems and Error-Correcting Codes
- scientific article; zbMATH DE number 3884178 (Why is no real title available?)
- scientific article; zbMATH DE number 3577144 (Why is no real title available?)
- scientific article; zbMATH DE number 1250549 (Why is no real title available?)
- scientific article; zbMATH DE number 1024657 (Why is no real title available?)
- scientific article; zbMATH DE number 2232233 (Why is no real title available?)
- Linear programming bounds for codes via a covering argument
- New upper bounds on sphere packings. I
- New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities
- On relations between covering radius and dual distance
- On the ratio of optimal integral and fractional covers
- Optima of dual integer linear programs
Cited in
(17)- Linear programming bounds for codes via a covering argument
- Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN
- Linear programming bounds for distributed storage codes
- Improved log-Sobolev inequalities, hypercontractivity and uncertainty principle on the hypercube
- High dimensional Hoffman bound and applications in extremal combinatorics
- Solving LPN Using Covering Codes
- Linear inequalities for covering codes. I. Pair covering inequalities
- Linear inequalities for covering codes. II. Triple covering inequalities
- An improvement of the Van Wee bound for binary linear covering codes
- scientific article; zbMATH DE number 1123782 (Why is no real title available?)
- Estimates of the neighborhood volumes of binary codes via their weight spectra
- Linear Programming Approximations for Index Coding
- On the optimum of Delsarte's linear program
- One more proof of the first linear programming bound for binary codes and two conjectures
- On linear codes which attain the Solomon-Stiffler bound
- Duality between packings and coverings of the Hamming space
- Bounds for short covering codes and reactive tabu search
This page was built for publication: Linear programming bounds for codes via a covering argument
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1017926)
