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. doi: 10.1109/18.850663. Google Scholar

[2]

C. Bachoc, Applications of semidefinite programming to coding theory,, in, (2010). Google Scholar

[3]

C. Bachoc, D. C. Gijswijt, A. Schrijver and F. Vallentin, Invariant semidefinite programs,, in, (2012), 219. Google Scholar

[4]

C. Bachoc and F. Vallentin, More semidefinite programming bounds (extended abstract),, in, (2007), 129. Google Scholar

[5]

C. Bachoc and F. Vallentin, New upper bounds for kissing numbers from semidefinite programming,, J. Amer. Math. Soc., 21 (2008), 909. 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). Google Scholar

[7]

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

[8]

C. F. Dunkl, An addition theorem for some $q$-Hahn polynomials,, Monatsh. Math., 85 (1977), 5. 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. 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. 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. 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. 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, (2003). Google Scholar

[14]

A. Khaleghi and F. R. Kschischang, Projective space codes for the injection metric,, in, (2009), 9. 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. Google Scholar

[16]

A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance,, in, (2008), 31. Google Scholar

[17]

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

[18]

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

[19]

F. Manganiello, E. Gorla and J. Rosenthal, Spread codes and spread decoding in network coding,, in, (2008), 851. 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. Google Scholar

[21]

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

[22]

A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming,, IEEE Trans. Inform. Theory, 51 (2005), 2859. 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. Google Scholar

[24]

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

[25]

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

[26]

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

[27]

H. Wang, C. Xing and R. Safavi-Naini, Linear authentication codes: bounds and constructions,, IEEE Trans. Inform. Theory, 49 (2003), 866. 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. 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. doi: 10.1109/18.850663. Google Scholar

[2]

C. Bachoc, Applications of semidefinite programming to coding theory,, in, (2010). Google Scholar

[3]

C. Bachoc, D. C. Gijswijt, A. Schrijver and F. Vallentin, Invariant semidefinite programs,, in, (2012), 219. Google Scholar

[4]

C. Bachoc and F. Vallentin, More semidefinite programming bounds (extended abstract),, in, (2007), 129. Google Scholar

[5]

C. Bachoc and F. Vallentin, New upper bounds for kissing numbers from semidefinite programming,, J. Amer. Math. Soc., 21 (2008), 909. 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). Google Scholar

[7]

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

[8]

C. F. Dunkl, An addition theorem for some $q$-Hahn polynomials,, Monatsh. Math., 85 (1977), 5. 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. 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. 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. 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. 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, (2003). Google Scholar

[14]

A. Khaleghi and F. R. Kschischang, Projective space codes for the injection metric,, in, (2009), 9. 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. Google Scholar

[16]

A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance,, in, (2008), 31. Google Scholar

[17]

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

[18]

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

[19]

F. Manganiello, E. Gorla and J. Rosenthal, Spread codes and spread decoding in network coding,, in, (2008), 851. 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. Google Scholar

[21]

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

[22]

A. Schrijver, New code upper bounds from the Terwilliger algebra and semidefinite programming,, IEEE Trans. Inform. Theory, 51 (2005), 2859. 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. Google Scholar

[24]

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

[25]

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

[26]

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

[27]

H. Wang, C. Xing and R. Safavi-Naini, Linear authentication codes: bounds and constructions,, IEEE Trans. Inform. Theory, 49 (2003), 866. 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. Google Scholar

[1]

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
[2]

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
[3]

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
[4]

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
[5]

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
[6]

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
[7]

Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019015
[8]

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
[9]

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
[10]

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
[11]

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
[12]

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
[13]

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
[14]

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
[15]

Karim Samei, Saadoun Mahmoudi. Singleton bounds for R-additive codes. Advances in Mathematics of Communications, 2018, 12 (1) : 107-114. doi: 10.3934/amc.2018006
[16]

Thomas Honold, Michael Kiermaier, Sascha Kurz. Constructions and bounds for mixed-dimension subspace codes. Advances in Mathematics of Communications, 2016, 10 (3) : 649-682. doi: 10.3934/amc.2016033
[17]

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
[18]

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
[19]

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
[20]

Emmanuel Charbit, Irène Charon, Gérard Cohen, Olivier Hudry, Antoine Lobstein. Discriminating codes in bipartite graphs: bounds, extremal cardinalities, complexity. Advances in Mathematics of Communications, 2008, 2 (4) : 403-420. doi: 10.3934/amc.2008.2.403

2018 Impact Factor: 0.879

Tools

Metrics

  • PDF downloads (6)
  • HTML views (0)
  • Cited by (7)

Other articles
by authors

[Back to Top]

Copyright © 2019 American Institute of Mathematical Sciences