Geodesic
Bounds for Codes by Semidefinite Programming
Informatics and Automation, Geometry, topology, and mathematical physics. I, Tome 263 (2008), pp. 143-158.

Voir la notice de l'article provenant de la source Math-Net.Ru

Delsarte's method and its extensions allow one to consider the upper bound problem for codes in two-point homogeneous spaces as a linear programming problem with perhaps infinitely many variables, which are the distance distribution. We show that using as variables power sums of distances, this problem can be considered as a finite semidefinite programming problem. This method allows one to improve some linear programming upper bounds. In particular, we obtain new bounds of one-sided kissing numbers. 
@article{TRSPY_2008_263_a10,
     author = {O. R. Musin},
     title = {Bounds for {Codes} by {Semidefinite} {Programming}},
     journal = {Informatics and Automation},
     pages = {143--158},
     publisher = {mathdoc},
     volume = {263},
     year = {2008},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/TRSPY_2008_263_a10/}
}
TY  - JOUR
AU  - O. R. Musin
TI  - Bounds for Codes by Semidefinite Programming
JO  - Informatics and Automation
PY  - 2008
SP  - 143
EP  - 158
VL  - 263
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/TRSPY_2008_263_a10/
LA  - en
ID  - TRSPY_2008_263_a10
ER  - 
%0 Journal Article
%A O. R. Musin
%T Bounds for Codes by Semidefinite Programming
%J Informatics and Automation
%D 2008
%P 143-158
%V 263
%I mathdoc
%U http://geodesic.mathdoc.fr/item/TRSPY_2008_263_a10/
%G en
%F TRSPY_2008_263_a10
O. R. Musin. Bounds for Codes by Semidefinite Programming. Informatics and Automation, Geometry, topology, and mathematical physics. I, Tome 263 (2008), pp. 143-158. http://geodesic.mathdoc.fr/item/TRSPY_2008_263_a10/

[1] Agrell E., Vardy A., Zeger K., “Upper bounds for constant-weight codes”, IEEE Trans. Inform. Theory, 46 (2000), 2373–2395 | DOI | MR | Zbl

[2] Bachoc C., Vallentin F., New upper bounds for kissing numbers from semidefinite programming, E-print , 2006 arxiv: math/0608426v4[math.MG] | MR

[3] Bachoc C., Vallentin F., Semidefinite programming, multivariate orthogonal polynomials, and codes in spherical caps, E-print , 2006 arxiv: math/0610856v2[math.MG] | MR

[4] Bannai E., Sloane N. J. A., “Uniqueness of certain spherical codes”, Canad. J. Math., 33 (1981), 437–449 | MR | Zbl

[5] Barg A., Musin O. R., “Codes in spherical caps”, Adv. Math. Commun., 1:1 (2007), 131–149 | DOI | MR | Zbl

[6] Bochner S., “Hilbert distances and positive definite functions”, Ann. Math., 42 (1941), 647–656 | DOI | MR | Zbl

[7] Boyvalenkov P., “Nonexistence of certain symmetric spherical codes”, Designs, Codes and Cryptogr., 3 (1993), 69–74 | DOI | MR | Zbl

[8] Conway J. H., Sloane N. J. A., Sphere packings, lattices and groups, 3rd ed., Springer, New York, 1999 | MR | Zbl

[9] Delsarte Ph., “Bounds for unrestricted codes, by linear programming”, Philips Res. Rep., 27 (1972), 272–289 | MR | Zbl

[10] Delsarte Ph., Goethals J. M., Seidel J. J., “Spherical codes and designs”, Geom. Dedicata, 6 (1977), 363–388 | MR | Zbl

[11] Gijswijt D., Schrijver A., Tanaka H., “New upper bounds for nonbinary codes based on the Terwilliger algebra and semidefinite programming”, J. Combin. Theory A, 113:8 (2006), 1719–1731 | DOI | MR | Zbl

[12] Kabatyanskii G. A., Levenshtein V. I., “O granitsakh dlya upakovok na sfere i v prostranstve”, Probl. pered. inform., 14:1 (1978), 3–25 | Zbl

[13] Krasikov I., Litsyn S., “Linear programming bounds for codes of small size”, Eur. J. Combin., 18 (1997), 647–656 | DOI | MR

[14] Levenshtein V. I., “O granitsakh dlya upakovok v $n$-mernom evklidovom prostranstve”, DAN SSSR, 245 (1979), 1299–1303 | MR

[15] Levenshtein V. I., “Universal bounds for codes and design”, Handbook of coding theory, V. 1, eds. V. Press, W. C. Huffman, Elsevier, Amsterdam, 1998, 499–648 | MR | Zbl

[16] Musin O. R., “Problema dvadtsati pyati sfer”, UMN, 58:4 (2003), 153–154 | MR | Zbl

[17] Musin O. R., “The kissing problem in three dimensions”, Discr. Comput. Geom., 35 (2006), 375–384 | DOI | MR | Zbl

[18] Musin O. R., “The kissing number in four dimensions”, Ann. Math., 168:1 (2008), 1–32 | DOI | MR | Zbl

[19] Musin O. R., “The one-sided kissing number in four dimensions”, Period. Math. Hungar., 53:1–2 (2006), 209–225 | DOI | MR | Zbl

[20] Musin O. R., Multivariate positive definite functions on spheres, E-print , 2007 arxiv: math/0701083v2[math.MG]

[21] Odlyzko A. M., Sloane N. J. A., “New bounds on the number of unit spheres that can touch a unit sphere in $n$ dimensions”, J. Combin. Theory A, 26 (1979), 210–214 | DOI | MR | Zbl

[22] Pfender F., “Improved Delsarte bounds for spherical codes in small dimensions”, J. Combin. Theory A, 114 (2007), 1133–1147 | DOI | MR | Zbl

[23] Pfender F., Ziegler G. M., “Kissing numbers, sphere packings, and some unexpected proofs”, Not. Amer. Math. Soc., 51 (2004), 873–883 | MR | Zbl

[24] Prasolov V. V., Mnogochleny, MTsNMO, M., 1999

[25] Rankin R. A., “The closest packing of spherical caps in $n$ dimensions”, Proc. Glasgow Math. Assoc., 2 (1955), 139–144 | DOI | MR | Zbl

[26] Schoenberg I. J., “Positive definite functions on spheres”, Duke Math. J., 9 (1942), 96–108 | DOI | MR | Zbl

[27] Schrijver A., “New code upper bounds from the Terwilliger algebra and semidefinite programming”, IEEE Trans. Inform. Theory, 51 (2005), 2859–2866 | DOI | MR

[28] Todd M. J., “Semidefinite optimization”, Acta numer., 10 (2001), 515–560 | DOI | MR | Zbl

[29] Vandenberghe L., Boyd S., “Semidefinite programming”, SIAM Rev., 38 (1996), 49–95 | DOI | MR | Zbl

[30] Wang H.-C., “Two-point homogeneous spaces”, Ann. Math., 55 (1952), 177–191 | DOI | MR | Zbl