Expander graphs, strong blocking sets and minimal codes

EUROCOMB’23

Abstract
We give a new explicit construction of strong blocking sets in finite projective spaces using expander graphs and asymptotically good linear codes. Using the recently found equivalence between strong blocking sets and linear minimal codes, we give the first explicit construction of $\mathbb{F}_q$-linear minimal codes of length $n$ and dimension $k$ such that $n$ is at most a constant times $q k$. This solves one of the main open problems on minimal codes.

Pages:
19–27
References

G. N. Alfarano, M. Borello, and A. Neri. A geometric characterization of minimal codes and their asymptotic performance. Advances in Mathematics of Communications, 16(1):115-133, 2022.
https://doi.org/10.3934/amc.2020104

G. N. Alfarano, M. Borello, and A. Neri. Outer strong blocking sets. arXiv:2301.09590, 2023.

G. N. Alfarano, M. Borello, A. Neri, and A. Ravagnani. Three combinatorial perspectives on minimal codes. SIAM Journal on Discrete Mathematics, 36(1):461-489, 2022.
https://doi.org/10.1137/21M1391493

N. Alon, A. Bishnoi, S. Das, and A. Neri. Strong blocking sets and minimal codes from expander graphs. arXiv:2305.15297, 2023.
https://doi.org/10.5817/CZ.MUNI.EUROCOMB23-003

Noga Alon. Explicit expanders of every degree and size. Combinatorica, 41:447-463, 2021.
https://doi.org/10.1007/s00493-020-4429-x

Noga Alon, Jehoshua Bruck, Joseph Naor, Moni Naor, and Ron M Roth. Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Transactions on Information Theory, 38(2):509-516, 1992.
https://doi.org/10.1109/18.119713

K. S. Bagga, L. W. Beineke, W. D. Goddard, M. J. Lipman, and R. E. Pippert. A survey of integrity. Discrete Applied Mathematics, 37:13-28, 1992.
https://doi.org/10.1016/0166-218X(92)90122-Q

József Balogh, Tamás Mészáros, and Adam Zsolt Wagner. Two results about the hypercube. Discrete Applied Mathematics, 247:322-326, 2018.
https://doi.org/10.1016/j.dam.2018.03.086

C. A. Barefoot, R. Entringer, and H. Swart. Vulnerability in graphs-a com parative survey. Journal of Combinatorial Mathematics and Combinatorial Computing, 1(38):13-22, 1987.

D. Bartoli and M. Bonini. Minimal linear codes in odd characteristic. IEEE Transactions on Information Theory, 65(7):4152-4155, 2019.
https://doi.org/10.1109/TIT.2019.2891992

D. Bartoli and M. Borello. Small strong blocking sets by concatenation. SIAM Journal on Discrete Mathematics, 37(1):65-82, 2023.
https://doi.org/10.1137/21M145032X

D. Bartoli, A. Cossidente, G. Marino, and Francesco Pavese. On cut- ting blocking sets and their codes. Forum Mathematicum, 34(2):347-368, 2022.
https://doi.org/10.1515/forum-2020-0338

D. Benko, C. Ernst, and D. Lanphier. Asymptotic bounds on the integrity of graphs and separator theorems for graphs. SIAM Journal on Discrete Mathematics, 23(1):265-277, 2009.
https://doi.org/10.1137/070692698

A. Bishnoi, J. D'haeseleer, D. Gijswijt, and A. Potukuchi. Blocking sets, minimal codes and trifferent codes. arXiv:2301.09457, 2023.

A. Blokhuis, P. Sziklai, and T. Szonyi. Blocking sets in projective spaces. Current research topics in Galois geometry, pages 61-84, 2011.

M. Bonini and M. Borello. Minimal linear codes arising from blocking sets. Journal of Algebraic Combinatorics, 53:327-341, 2021.
https://doi.org/10.1007/s10801-019-00930-6

A. E Brouwer and A. Schrijver. The blocking number of an affine space. Journal of Combinatorial Theory, Series A, 24(2):251-253, 1978.
https://doi.org/10.1016/0097-3165(78)90013-4

H. Chabanne, G. Cohen, and A. Patey. Towards secure two-party computation from the wire-tap channel. In International Conference on Information Security and Cryptology, pages 34-46. Springer, 2013.
https://doi.org/10.1007/978-3-319-12160-4_3

G. Cohen, S. Mesnager, and H. Randriam. Yet another variation on minimal linear codes. Advances in Mathematics of Communications, 10(1):53-61, 2016.
https://doi.org/10.3934/amc.2016.10.53

G. D. Cohen, S. Mesnager, and A. Patey. On minimal and quasi-minimal linear codes. In IMA International Conference on Cryptography and Coding, pages 85-98. Springer, 2013.
https://doi.org/10.1007/978-3-642-45239-0_6

A. A. Davydov, M. Giulietti, S. Marcugini, and F. Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communi- cations, 5(1):119-147, 2011.
https://doi.org/10.3934/amc.2011.5.119

C. Ding. Linear codes from some 2-designs. IEEE Transactions on Information Theory, 61(6):3265-3275, 2015.
https://doi.org/10.1109/TIT.2015.2420118

S. Fancsali and P. Sziklai. Lines in higgledy-piggledy arrangement. Electronic Journal of Combinatorics, 21, 2014.
https://doi.org/10.37236/4149

T. Héger and Z. L. Nagy. Short minimal codes and covering codes via strong blocking sets in projective spaces. IEEE Transactions on Information Theory, 68(2):881-890, 2021.
https://doi.org/10.1109/TIT.2021.3123730

T. Héger, B. Patkós, and M. Takáts. Search problems in vector spaces. Designs, Codes and Cryptography, 76(2):207-216, 2015.
https://doi.org/10.1007/s10623-014-9941-9

S. Hoory, N. Linial, and A. Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 43(4):439-561, 2006.
https://doi.org/10.1090/S0273-0979-06-01126-8

Tai-Yang Hwang. Decoding linear block codes for minimizing word error rate (corresp.). IEEE Transactions on Information Theory, 25(6):733-737, 1979.
https://doi.org/10.1109/TIT.1979.1056120

J. Justesen. Class of constructive asymptotically good algebraic codes. IEEE Trans- actions on Information Theory, 18(5):652-656, 1972.
https://doi.org/10.1109/TIT.1972.1054893

J. L. Massey. Minimal codewords and secret sharing. In Proceedings of the 6th joint Swedish-Russian international workshop on information theory, pages 276-279, 1993.

D Miklós. Linear binary codes with intersection properties. Discrete Applied Mathemat- ics, 9(2):187-196, 1984.
https://doi.org/10.1016/0166-218X(84)90018-0

M. Sipser and D. A. Spielman. Expander codes. IEEE Transactions on Infor- mation Theory, 42(6):1710-1722, 1996.
https://doi.org/10.1109/18.556667

C. Tang, Y. Qiu, Q. Liao, and Z. Zhou. Full characterization of minimal linear codes as cutting blocking sets. IEEE Transactions on Information Theory, 67(6):3690-3700, 2021.
https://doi.org/10.1109/TIT.2021.3070377

R. Tanner. A recursive approach to low complexity codes. IEEE Transactions on Infor- mation Theory, 27(5):533-547, 1981.
https://doi.org/10.1109/TIT.1981.1056404

Metrics

0

Views

0

PDF views