Computer Science/Discrete Mathematics Seminar II

A binary code is simply any subset of 0/1 strings of a fixed length. Given two strings, a standard way of defining their distance is by counting the number of positions in which they disagree. Roughly speaking, if elements of a code are sufficiently far apart, then the code is resilient to errors. However, requiring a large minimum distance reduces the maximum possible size of a code. Finding precise trade-offs between minimum distance and maximum size of binary codes remains a longstanding open problem.

In this talk, we plan to give a brief introduction to this problem surveying some known size bounds for binary codes given a minimum distance requirement. The best existential bounds come from simple probabilistic arguments dating back to 1950s. In contrast, the best impossibility bounds come from a careful theoretical analysis, dating back to 1970s, of Delsarte's linear programs. There is an exponential gap between these bounds.

We will also discuss a new linear programming hierarchy tailored to linear codes. This hierarchy is structurally similar to Delsarte's linear programs, coinciding with them at its first level, but proven to converge to the maximum possible size of a linear code given a distance requirement.

This new hierarchy is based on joint work with Leonardo Coregliano and Chris Jones.