Computer Science/Discrete Mathematics Seminar I
Probabilistic Guarantees to Explicit Constructions: Local Properties of Linear Codes
We present a general framework for derandomizing random linear codes with respect to a broad class of properties, known as local properties, which encompass several standard notions such as minimum distance, list-decoding, list-recovery, and perfect hashing. Our approach extends the classical Alon-Edmonds-Luby (AEL) construction through a modified formalism of local coordinate-wise linear (LCL) properties, introduced by Levi, Mosheiff, and Shagrithaya (FOCS 2025).
The main result shows that we can obtain explicit constructions of codes achieving LCL properties at the same level of optimality as random linear codes, with the cost of increased alphabet size. This gives the first explicit constructions of list-recoverable codes having output list sizes that match those of random linear codes, among other results.
In this talk we will give the necessary background required to formulate the main result, as well as a sketch of its proof.
Based on joint work with Fernando Granha Jeronimo.