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]

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

Julian Koellermeier, Giovanni Samaey. Projective integration schemes for hyperbolic moment equations. Kinetic & Related Models, , () : -. doi: 10.3934/krm.2021008
[3]

Meng Chen, Yong Hu, Matteo Penegini. On projective threefolds of general type with small positive geometric genus. Electronic Research Archive, , () : -. doi: 10.3934/era.2020117
[4]

Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2020  doi: 10.3934/fods.2020018
[5]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054
[6]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[7]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001
[8]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012
[9]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136
[10]

Klemens Fellner, Jeff Morgan, Bao Quoc Tang. Uniform-in-time bounds for quadratic reaction-diffusion systems with mass dissipation in higher dimensions. Discrete & Continuous Dynamical Systems - S, 2021, 14 (2) : 635-651. doi: 10.3934/dcdss.2020334
[11]

Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020124
[12]

Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162
[13]

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013
[14]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118
[15]

Vito Napolitano, Ferdinando Zullo. Codes with few weights arising from linear sets. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020129
[16]

Dandan Wang, Xiwang Cao, Gaojun Luo. A class of linear codes and their complete weight enumerators. Advances in Mathematics of Communications, 2021, 15 (1) : 73-97. doi: 10.3934/amc.2020044
[17]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045
[18]

Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053
[19]

Nicola Pace, Angelo Sonnino. On the existence of PD-sets: Algorithms arising from automorphism groups of codes. Advances in Mathematics of Communications, 2021, 15 (2) : 267-277. doi: 10.3934/amc.2020065
[20]

Jong Yoon Hyun, Boran Kim, Minwon Na. Construction of minimal linear codes from multi-variable functions. Advances in Mathematics of Communications, 2021, 15 (2) : 227-240. doi: 10.3934/amc.2020055

2019 Impact Factor: 0.734

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences