Bounds for projective codes from semidefinite programming

Christine Bachoc; Alberto Passuello; Frank Vallentin

doi:10.3934/amc.2013.7.127

Article Contents

2013, Volume 7, Issue 2: 127-145. Doi: 10.3934/amc.2013.7.127

This issue Previous Article Even periodic and odd periodic complementary sequence pairs from generalized Boolean functions Next Article Isometry and automorphisms of constant dimension codes

Bounds for projective codes from semidefinite programming

1.
University of Bordeaux, Institut de Mathématiques, 351, cours de la Libération, F-33400 Talence
2.
Mathematisches Institut, Universität zu Köln, Weyertal 86-90, 50931 Köln

Received: May 2012

Published: May 2013

Abstract / Introduction Related Papers Cited by

Abstract

We apply the semidefinite programming method to derive bounds for projective codes over a finite field.

Keywords:

Mathematics Subject Classification: 94B65, 90C22.

Citation:

Related Papers

Cited by

References

[1]	R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung, Network information flow, IEEE Trans. Inform. Theory, 46 (2000), 1204-1216.doi: 10.1109/18.850663.
[2]	C. Bachoc, Applications of semidefinite programming to coding theory, in "IEEE Information Theory Workshop (ITW),'' 2010.
[3]	C. Bachoc, D. C. Gijswijt, A. Schrijver and F. Vallentin, Invariant semidefinite programs, in "Handbook on Semidefinite, Conic and Polynomial Optimization'' (eds. M.F. Anjos and J.B. Lasserre), Springer, (2012), 219-269.
[4]	C. Bachoc and F. Vallentin, More semidefinite programming bounds (extended abstract), in "COE Conference on the Development of Dynamic Mathematics with High Functionality,'' Fukuoka, (2007), 129-132.
[5]	C. Bachoc and F. Vallentin, New upper bounds for kissing numbers from semidefinite programming, J. Amer. Math. Soc., 21 (2008), 909-924.doi: 10.1090/S0894-0347-07-00589-9.
[6]	P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., (1973), 97 pp.
[7]	P. Delsarte, Hahn polynomials, discrete harmonics and $t$-designs, SIAM J. Appl. Math., 34 (1978), 157-166.
[8]	C. F. Dunkl, An addition theorem for some $q$-Hahn polynomials, Monatsh. Math., 85 (1977), 5-37.
[9]	T. Etzion and N. Silberstein, Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Trans. Inform. Theory, 55 (2009), 2909-2919.doi: 10.1109/TIT.2009.2021376.
[10]	T. Etzion and A. Vardy, Error-correcting codes in projective space, IEEE Trans. Inform. Theory, 57 (2011), 1165-1173.
[11]	P. Frankl and R. M. Wilson, The Erdős-Ko-Rado theorem for vector spaces, J. Combin. Theory Ser. A, 43 (1986), 228-236.
[12]	D. C. Gijswijt, H. D. Mittelmann and A. Schrijver, Semidefinite code bounds based on quadruple distances, IEEE Trans. Inform. Theory, 58 (2012), 2697-2705.doi: 10.1109/TIT.2012.2184845.
[13]	T. Ho, R. Koetter, M. Médard, D. R. Karger and M. Effros, The benefits of coding over routing in a randomized setting, in "Proc. IEEE ISIT'03,'' 2003.
[14]	A. Khaleghi and F. R. Kschischang, Projective space codes for the injection metric, in "Proc. 11th Canadian Workshop Inform. Theory,'' (2009), 9-12.
[15]	R. Koetter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3579-3591.
[16]	A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance, in "Mathematical Methods in Computer Science,'' Springer, Berlin, (2008), 31-42.
[17]	F. R. Kschischang and D. Silva, On metrics for error correction in network coding, IEEE Trans. Inform. Theory, 55 (2009), 5479-5490.
[18]	L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25 (1979), 1-5.
[19]	F. Manganiello, E. Gorla and J. Rosenthal, Spread codes and spread decoding in network coding, in "Proceedings of the 2008 IEEE International Symposium on Information,'' (2008), 851-855.
[20]	R. J. McEliece, E. R. Rodemich and H. C. Rumsey Jr., The Lovász bound and some generalizations, J. Combin. Inform. Sys. Sci., 3 (1978), 134-152.
[21]	A. Schrijver, A comparison of the Delsarte and Lovász bound, IEEE Trans. Inform. Theory, 25 (1979), 425-429.
[22]	A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming, IEEE Trans. Inform. Theory, 51 (2005), 2859-2866.doi: 10.1109/TIT.2005.851748.
[23]	M. Schwartz and T. Etzion, Codes and anticodes in the Grassmann graph, J. Combin. Theory Ser. A, 97 (2002), 27-42.
[24]	M. J. Todd, Semidefinite optimization, Acta Numerica, 10 (2001), 515-560.
[25]	F. Vallentin, Symmetry in semidefinite programs, Linear Algebra Appl., 430 (2009), 360-369.
[26]	L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Rev., 38 (1996), 49-95.
[27]	H. Wang, C. Xing and R. Safavi-Naini, Linear authentication codes: bounds and constructions, IEEE Trans. Inform. Theory, 49 (2003), 866-872.doi: 10.1109/TIT.2003.809567.
[28]	S. T. Xia and F. W. Fu, Johnson type bounds on constant dimension codes, Des. Codes Crypt., 50 (2009), 163-172.