American Institute of Mathematical Sciences

Advanced
May  2013, 7(2): 127-145. doi: 10.3934/amc.2013.7.127

Bounds for projective codes from semidefinite programming

Christine Bachoc 1, , Alberto Passuello 1, and  Frank Vallentin 2,

1. 

University of Bordeaux, Institut de Mathématiques, 351, cours de la Libération, F-33400 Talence, France, France
2. 

Mathematisches Institut, Universität zu Köln, Weyertal 86-90, 50931 Köln, Germany

Received  May 2012 Published  May 2013

We apply the semidefinite programming method to derive bounds for projective codes over a finite field.
Keywords: semidefinite programming, bounds., Projective codes.
Mathematics Subject Classification: 94B65, 90C2.
Citation: Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127
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.  Google Scholar

[2]

C. Bachoc, Applications of semidefinite programming to coding theory, in "IEEE Information Theory Workshop (ITW),'' 2010. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[6]

P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., (1973), 97 pp.  Google Scholar

[7]

P. Delsarte, Hahn polynomials, discrete harmonics and $t$-designs, SIAM J. Appl. Math., 34 (1978), 157-166.  Google Scholar

[8]

C. F. Dunkl, An addition theorem for some $q$-Hahn polynomials, Monatsh. Math., 85 (1977), 5-37.  Google Scholar

[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.  Google Scholar

[10]

T. Etzion and A. Vardy, Error-correcting codes in projective space, IEEE Trans. Inform. Theory, 57 (2011), 1165-1173.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[14]

A. Khaleghi and F. R. Kschischang, Projective space codes for the injection metric, in "Proc. 11th Canadian Workshop Inform. Theory,'' (2009), 9-12. Google Scholar

[15]

R. Koetter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3579-3591.  Google Scholar

[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.  Google Scholar

[17]

F. R. Kschischang and D. Silva, On metrics for error correction in network coding, IEEE Trans. Inform. Theory, 55 (2009), 5479-5490.  Google Scholar

[18]

L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25 (1979), 1-5.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[21]

A. Schrijver, A comparison of the Delsarte and Lovász bound, IEEE Trans. Inform. Theory, 25 (1979), 425-429.  Google Scholar

[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.  Google Scholar

[23]

M. Schwartz and T. Etzion, Codes and anticodes in the Grassmann graph, J. Combin. Theory Ser. A, 97 (2002), 27-42.  Google Scholar

[24]

M. J. Todd, Semidefinite optimization, Acta Numerica, 10 (2001), 515-560.  Google Scholar

[25]

F. Vallentin, Symmetry in semidefinite programs, Linear Algebra Appl., 430 (2009), 360-369.  Google Scholar

[26]

L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Rev., 38 (1996), 49-95.  Google Scholar

[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.  Google Scholar

[28]

S. T. Xia and F. W. Fu, Johnson type bounds on constant dimension codes, Des. Codes Crypt., 50 (2009), 163-172.  Google Scholar

show all references

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

[2]

C. Bachoc, Applications of semidefinite programming to coding theory, in "IEEE Information Theory Workshop (ITW),'' 2010. Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[6]

P. Delsarte, An algebraic approach to the association schemes of coding theory, Philips Res. Rep. Suppl., (1973), 97 pp.  Google Scholar

[7]

P. Delsarte, Hahn polynomials, discrete harmonics and $t$-designs, SIAM J. Appl. Math., 34 (1978), 157-166.  Google Scholar

[8]

C. F. Dunkl, An addition theorem for some $q$-Hahn polynomials, Monatsh. Math., 85 (1977), 5-37.  Google Scholar

[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.  Google Scholar

[10]

T. Etzion and A. Vardy, Error-correcting codes in projective space, IEEE Trans. Inform. Theory, 57 (2011), 1165-1173.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[14]

A. Khaleghi and F. R. Kschischang, Projective space codes for the injection metric, in "Proc. 11th Canadian Workshop Inform. Theory,'' (2009), 9-12. Google Scholar

[15]

R. Koetter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3579-3591.  Google Scholar

[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.  Google Scholar

[17]

F. R. Kschischang and D. Silva, On metrics for error correction in network coding, IEEE Trans. Inform. Theory, 55 (2009), 5479-5490.  Google Scholar

[18]

L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inform. Theory, 25 (1979), 1-5.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[21]

A. Schrijver, A comparison of the Delsarte and Lovász bound, IEEE Trans. Inform. Theory, 25 (1979), 425-429.  Google Scholar

[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.  Google Scholar

[23]

M. Schwartz and T. Etzion, Codes and anticodes in the Grassmann graph, J. Combin. Theory Ser. A, 97 (2002), 27-42.  Google Scholar

[24]

M. J. Todd, Semidefinite optimization, Acta Numerica, 10 (2001), 515-560.  Google Scholar

[25]

F. Vallentin, Symmetry in semidefinite programs, Linear Algebra Appl., 430 (2009), 360-369.  Google Scholar

[26]

L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Rev., 38 (1996), 49-95.  Google Scholar

[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.  Google Scholar

[28]

S. T. Xia and F. W. Fu, Johnson type bounds on constant dimension codes, Des. Codes Crypt., 50 (2009), 163-172.  Google Scholar

[1]

Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 613-630. doi: 10.3934/amc.2020034
[2]

Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323
[3]

Ali Tebbi, Terence Chan, Chi Wan Sung. Linear programming bounds for distributed storage codes. Advances in Mathematics of Communications, 2020, 14 (2) : 333-357. doi: 10.3934/amc.2020024
[4]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881
[5]

Idan Goldenberg, David Burshtein. Error bounds for repeat-accumulate codes decoded via linear programming. Advances in Mathematics of Communications, 2011, 5 (4) : 555-570. doi: 10.3934/amc.2011.5.555
[6]

Beniamin Mounits, Tuvi Etzion, Simon Litsyn. New upper bounds on codes via association schemes and linear programming. Advances in Mathematics of Communications, 2007, 1 (2) : 173-195. doi: 10.3934/amc.2007.1.173
[7]

Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010
[8]

Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015
[9]

Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187
[10]

Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
[11]

Jesús Carrillo-Pacheco, Felipe Zaldivar. On codes over FFN$(1,q)$-projective varieties. Advances in Mathematics of Communications, 2016, 10 (2) : 209-220. doi: 10.3934/amc.2016001
[12]

Cristian Dobre. Mathematical properties of the regular *-representation of matrix $*$-algebras with applications to semidefinite programming. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 367-378. doi: 10.3934/naco.2013.3.367
[13]

Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119
[14]

Jop Briët, Assaf Naor, Oded Regev. Locally decodable codes and the failure of cotype for projective tensor products. Electronic Research Announcements, 2012, 19: 120-130. doi: 10.3934/era.2012.19.120
[15]

Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[16]

Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651
[17]

Chenchen Wu, Dachuan Xu, Xin-Yuan Zhao. An improved approximation algorithm for the $2$-catalog segmentation problem using semidefinite programming relaxation. Journal of Industrial & Management Optimization, 2012, 8 (1) : 117-126. doi: 10.3934/jimo.2012.8.117
[18]

Olav Geil, Carlos Munuera, Diego Ruano, Fernando Torres. On the order bounds for one-point AG codes. Advances in Mathematics of Communications, 2011, 5 (3) : 489-504. doi: 10.3934/amc.2011.5.489
[19]

San Ling, Buket Özkaya. New bounds on the minimum distance of cyclic codes. Advances in Mathematics of Communications, 2021, 15 (1) : 1-8. doi: 10.3934/amc.2020038
[20]

Christine A. Kelley, Deepak Sridhara. Eigenvalue bounds on the pseudocodeword weight of expander codes. Advances in Mathematics of Communications, 2007, 1 (3) : 287-306. doi: 10.3934/amc.2007.1.287

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (90)
  • HTML views (0)
  • Cited by (11)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences