Linear Programming Bounds for Codes via a Covering Argument

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 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.

• Publication year

  2007

• Venue

  Electron. Colloquium Comput. Complex.

• Publication date

  2007-02-14

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/s00454-008-9128-0arXiv math/0702425
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A modified logarithmic Sobolev inequality for the Hamming cube and some applications

  2008influential reference
• Generalized Alon--Boppana Theorems and Error-Correcting Codes

  2005cited by this paper
• Covering Codes

  2005cited by this paper
• On Delsarte's linear programming bounds for binary codes

  2005cited by this paper
• Linear Codes with Covering Radius and Codimension

  2001cited by this paper
• New upper bounds on sphere packings I

  2001cited by this paper
• On relations between covering radius and dual distance

  1999influential reference
• Universal bounds for codes and designs, in Handbookof Coding Theory

  1998cited by this paper
• Lower bounds for spherical designs

  1997cited by this paper
• An upper bound on the covering radius as a function of the dual distance

  1990cited by this paper
• A personal communication

  1989influential reference
• Optima of dual integer linear programs

  1988cited by this paper
• The influence of variables on Boolean functions

  1988cited by this paper
• A Fast and Simple Randomized Parallel Algorithm for the Maximal Independent Set Problem

  1985cited by this paper
• Algebraic Combinatorics I: Association Schemes

  1984cited by this paper
• Introduction to coding theory

  1982cited by this paper
• New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities

  1977influential reference
• On orthogonal polynomials

  1975cited by this paper
• On the ratio of optimal integral and fractional covers

  1975cited by this paper
• Theory of Error-correcting Codes

  year unknowncited by this paper

• Higher-order Delsarte Dual LPs: Lifting, Constructions and Completeness

  2025cites this paper
• New upper bounds for binary linear covering codes

  2025cites this paper
• On the Complexity of Decoded Quantum Interferometry

  2025cites this paper
• New Solutions to Delsarte’s Dual Linear Programs

  2024cites this paper
• Binary Codes with Distance Close to Half

  2024influential citation
• SIGACT News Complexity Theory Column

  2024influential citation
• An Elementary Proof of the First LP Bound on the Rate of Binary Codes

  2023cites this paper
• A Version of Delsarte's Linear Program for Constrained Systems

  2023cites this paper
• New Bounds on the Size of Binary Codes With Large Minimum Distance

  2023influential citation
• Rényi–Sobolev Inequalities and Connections to Spectral Graph Theory

  2023cites this paper
• Estimating the Sizes of Binary Error-Correcting Constrained Codes

  2023cites this paper
• New LP-based Upper Bounds in the Rate-vs.-Distance Problem for Linear Codes

  2022cites this paper
• New Bounds on the Size of Binary Codes with Large Minimum Distance

  2022influential citation
• New LP-Based Upper Bounds in the Rate-Vs.-Distance Problem for Binary Linear Codes

  2022cites this paper
• Generalized Singleton Type Upper Bounds

  2022cites this paper
• Exact Completeness of LP Hierarchies for Linear Codes

  2022cites this paper
• Linear Programming Hierarchies in Coding Theory: Dual Solutions

  2022cites this paper
• Bounds on Mixed Codes with Finite Alphabets

  2022cites this paper
• One more proof of the first linear programming bound for binary codes and two conjectures

  2021cites this paper
• A Complete Linear Programming Hierarchy for Linear Codes

  2021cites this paper
• List-decodable Codes and Covering Codes

  2021cites this paper
• Unique Decoding of Explicit $\varepsilon$-balanced Codes Near the Gilbert-Varshamov Bound

  2020cites this paper
• Unique Decoding of Explicit ε-balanced Codes Near the Gilbert-Varshamov Bound

  2020cites this paper
• High dimensional Hoffman bound and applications in extremal combinatorics

  2019cites this paper
• Generalized List Decoding

  2019cites this paper
• On the weight distribution of random binary linear codes

  2018cites this paper
• A Note on the Joint Entropy of N/2-Wise Independence

  2018influential citation
• An Entropy Lower Bound for Non-Malleable Extractors

  2018influential citation
• The Linear-Programming Bound

  2017cites this paper
• A short note on the joint entropy of n/2-wise independence

  2017influential citation
• On the Covering Radius of Small Codes Versus Dual Distance

  2017cites this paper
• Improved log-Sobolev inequalities, hypercontractivity and uncertainty principle on the hypercube

  2016cites this paper
• Linear programming upper bounds on permutation code sizes from coherent configurations related to the Kendall-tau distance metric

  2012cites this paper
• Coding-theoretic methods for sparse recovery

  2011cites this paper
• Lower bounds for designs in symmetric spaces

  2010cites this paper
• ALGEBRAIC COMBINATORICS

  year unknowncites this paper