Computer Science/Discrete Mathematics Seminar II

One of the central problems of coding theory is to determine the trade-off between the amount of information a code can carry (captured by its rate) and its robustness to resist message corruption (captured by its distance). On the existential side, Gilbert and Varshamov showed in the 1950s that random codes and random linear codes achieve a considerably good trade-off; this is known as the GV bound. On the impossibility side, McEliece, Rodemich, Rumsey and Welch (MRRW) in the 1970s provided an upper bound, known as LP bound, by analyzing the Delsarte linear programs corresponding to the Hamming and Johnson association schemes. However, there is still a significant gap between these lower and upper bounds.

In a recent work with Fernando Jeronimo and Chris Jones, we provided a hierarchy of higher-order Hamming schemes that is complete for linear codes. Namely, in a high enough level of the hierarchy the corresponding Delsarte linear program gives tight bounds for the size of linear codes.

In this first lecture, I will go over the basics of the theory of association schemes needed to understand our result (and as such no prior knowledge of this theory is required).