zbMATH — the first resource for mathematics

Linear programming bounds for codes via a covering argument. (English) Zbl 1173.90475
Summary: 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.

90C05 Linear programming
94B99 Theory of error-correcting codes and error-detecting codes
65T50 Numerical methods for discrete and fast Fourier transforms
Full Text: DOI arXiv
[1] Aharoni, R.; Erdos, P.; Linial, N., Optima of dual integer linear programs, Combinatorica, 8, 13-20, (1988) · Zbl 0648.90054
[2] Alon, N.; Babai, L.; Itai, A., A fast and simple randomized parallel algorithm for the maximal independent set problem, J. Algorithms, 7, 567-583, (1986) · Zbl 0631.68063
[3] Ashkihmin, A.; Honkala, I.; Laihonen, T.; Litsyn, S., On relations between covering radius and dual distance, IEEE Trans. Inf. Theory, IT-45, 1808-1816, (1999) · Zbl 0959.94037
[4] Bannai, E., Ito, T.: Algebraic Combinatorics I: Association Schemes. Benjamin-Cummings, Redwood City (1984) · Zbl 0555.05019
[5] Cohen, G., Honkala, I., Litsyn, S., Lobstein, A.: Covering Codes. Elsevier, Amsterdam (1997) · Zbl 0874.94001
[6] Cohn, H.; Elkies, N., New upper bounds for sphere packings I, Ann. Math., 157, 689-714, (2003) · Zbl 1041.52011
[7] Delsarte, P.: An algebraic approach to the association schemes of coding theory. Philips Res. Rep., Suppl. 10 (1973) · Zbl 1075.05606
[8] Friedman, J., Tillich, J.-P.: Generalized Alon-Boppana theorems and error-correcting codes. Preprint (2002) · Zbl 1096.68120
[9] Kahn, J., Kalai, G., Linial, N.: The influence of variables on Boolean functions. In: FOCS, pp. 68-80. (1988)
[10] Kalai, G., Linial, N.: Personal communication
[11] Levenshtein, V. I.; Pless, V. S. (ed.); Huffman, W. C. (ed.), Universal bounds for codes and designs, (1998), Elsevier
[12] Lovasz, L., On the ratio of optimal integral and fractional covers, Discrete Math., 13, 383-390, (1975) · Zbl 0323.05127
[13] MacWilliams, J., Sloane, N.J.A.: The Theory of Error Correcting Codes. Amsterdam, North-Holland (1977) · Zbl 0369.94008
[14] McEliece, R. J.; Rodemich, E. R.; Rumsey, H.; Welch, L. R., New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities, IEEE Trans. Inf. Theory, IT-23, 157-166, (1977) · Zbl 0361.94016
[15] Navon, M., Samorodnitsky, A.: On Delsarte’s linear programming bounds for binary codes. In: Proceedings of FOCS 46 · Zbl 1173.90475
[16] Samorodnitsky, A.: The proof of the first JPL bound for association schemes via formal Fourier transform. Manuscript (2006)
[17] Samorodnitsky, A.: A modified logarithmic Sobolev inequality for the Hamming cube and some applications. arXiv:0807.1679 (2008)
[18] van Lint, J.H.: Introduction to Coding Theory, 3rd edn. Springer, Berlin (1999) · Zbl 0936.94014
[19] Szegö, G.: Orthogonal Polynomials. Am. Math. Soc., Providence (1939) · JFM 65.0286.02
[20] Tietavainen, A., Upper bound on the covering radius of a code as a function of its dual distance, IEEE Trans. Inf. Theory, IT-36, 1472-1474, (1990) · Zbl 0713.94019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.