Strong blocking sets and minimal codes from expander graphs

MaRDI QIDQ6437846zbMATH OpenFDO

Authors Noga Alon, Anurag Bishnoi, Shagnik Das, Alessandro Neri

Publication date 24 May 2023

Abstract: A strong blocking set in a finite projective space is a set of points that intersects each hyperplane in a spanning set. We provide a new graph theoretic construction of such sets: combining constant-degree expanders with asymptotically good codes, we explicitly construct strong blocking sets in the $(k-1)$-dimensional projective space over $mathbb{F}_q$ that have size $O(qk)$. Since strong blocking sets have recently been shown to be equivalent to minimal linear codes, our construction gives the first explicit construction of $mathbb{F}_q$-linear minimal codes of length $n$ and dimension $k$, for every prime power $q$, for which $n=O(qk)$. This solves one of the main open problems on minimal codes.

This page was built for publication: Strong blocking sets and minimal codes from expander graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6437846)