Expander graphs, strong blocking sets and minimal codes
EUROCOMB’23
19–27
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
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
Copyright © 2023 Noga Alon, Anurag Bishnoi, Shagnik Das, Alessandro Neri