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

Bounds for projective codes from semidefinite programming

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

[2]

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

[3]

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

[4]

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

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

[6]

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

[7]

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

[8]

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

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

[10]

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

[11]

P. Frankl and R. M. Wilson, The Erdős-Ko-Rado theorem for vector spaces,, J. Combin. Theory Ser. A, 43 (1986), 228.

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

[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).

[14]

A. Khaleghi and F. R. Kschischang, Projective space codes for the injection metric,, in, (2009), 9.

[15]

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

[16]

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

[17]

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

[18]

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

[19]

F. Manganiello, E. Gorla and J. Rosenthal, Spread codes and spread decoding in network coding,, in, (2008), 851.

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

[21]

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

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

[23]

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

[24]

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

[25]

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

[26]

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

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

[28]

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

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.

[2]

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

[3]

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

[4]

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

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

[6]

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

[7]

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

[8]

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

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

[10]

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

[11]

P. Frankl and R. M. Wilson, The Erdős-Ko-Rado theorem for vector spaces,, J. Combin. Theory Ser. A, 43 (1986), 228.

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

[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).

[14]

A. Khaleghi and F. R. Kschischang, Projective space codes for the injection metric,, in, (2009), 9.

[15]

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

[16]

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

[17]

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

[18]

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

[19]

F. Manganiello, E. Gorla and J. Rosenthal, Spread codes and spread decoding in network coding,, in, (2008), 851.

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

[21]

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

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

[23]

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

[24]

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

[25]

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

[26]

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

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

[28]

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

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

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

[8]

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

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

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

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

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

Christine Bachoc, Gilles Zémor. Bounds for binary codes relative to pseudo-distances of $k$ points. Advances in Mathematics of Communications, 2010, 4 (4) : 547-565. doi: 10.3934/amc.2010.4.547

[20]

Ferruh Özbudak, Patrick Solé. Gilbert-Varshamov type bounds for linear codes over finite chain rings. Advances in Mathematics of Communications, 2007, 1 (1) : 99-109. doi: 10.3934/amc.2007.1.99

2016 Impact Factor: 0.8

Metrics

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

[Back to Top]