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
- 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?)
- 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
- 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)- On the optimum of Delsarte's linear program
- scientific article; zbMATH DE number 1123782 (Why is no real title available?)
- Improved log-Sobolev inequalities, hypercontractivity and uncertainty principle on the hypercube
- One more proof of the first linear programming bound for binary codes and two conjectures
- Linear programming bounds for distributed storage codes
- Linear programming bounds for codes via a covering argument
- Duality between packings and coverings of the Hamming space
- An improvement of the Van Wee bound for binary linear covering codes
- Linear Programming Approximations for Index Coding
- Bounds for short covering codes and reactive tabu search
- Linear inequalities for covering codes. II. Triple covering inequalities
- High dimensional Hoffman bound and applications in extremal combinatorics
- Smoothing out binary linear codes and worst-case sub-exponential hardness for LPN
- Solving LPN Using Covering Codes
- Estimates of the neighborhood volumes of binary codes via their weight spectra
- On linear codes which attain the Solomon-Stiffler bound
- Linear inequalities for covering codes. I. Pair covering inequalities
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)
