Around Reed-Muller codes
Presenter
August 20, 2025
Abstract
(I) Reed-Muller (RM) codes form a classic code family that continues to inspire new results and a seemingly inexhaustible range of problems. In this minicourse we discuss several problems inspired by recent works. The first of them concerns storage codes on graphs. A storage code is a set of assignments of bits to the vertices of a graph such that every vertex satisfies a parity check defined by its neighbors. Assuming that the graph is triangle-free (we will explain this assumption), what is the largest-size storage code on it? It was recently shown that there exist graphs on n vertices for which such codes attain the maximum possible size, close to 2^n (arXiv:2212.12117). It is still an open question whether RM codes give rise to similar constructions. (II) RM codes can also be defined from cosets of the subgroups of the additive group Z_2^m. This construction can be extended to other finite groups of a similar kind, known as Coxeter groups. These groups are not too mysterious: for instance, the permutation group is one of them. It is of interest to explore properties of such Coxeter codes (arXiv:2502.14746). For instance, can we extend the famous |u|u+v| construction? If so, can one construct some analogs of recent decoders of RM codes? More challenging: RM codes achieve the Shannon capacity of the binary erasure channel. Do other Coxeter codes share this property? Also challenging: prove the distance value of Coxeter codes (we have a good idea of the answer).