A proof of the RM code capacity conjecture

-
Emmanuel Abbe, EPFL
Fine Hall 314

In 1948, Shannon used a probabilistic argument to prove the existence of codes achieving channel capacity. In 1954, Muller and Reed introduced a simple deterministic code construction, conjectured shortly after to achieve channel capacity. Major progress was made towards establishing this conjecture over the last decades, with various areas of discrete mathematics involved. In particular, the special case of the erasure channel was settled in 2015 by Kudekar at al., relying on Bourgain-Kalai's sharp threshold theorem for symmetric monotone properties. The main case of error channels remained however open, due in particular to the property being non-monotone, and the absence of techniques to obtain fast local error decay. In this talk, we provide a proof of the general conjecture. The proof circumvents the use of Bourgain-Kalai's theorem by establishing first a "weak" threshold property that relies solely on symmetries. The proof then proceeds with a boosting framework to improve the weak local error into a strong global error, relying on sunflower structures as defined in Erdős-Rado but for subspaces. Joint work with Colin Sandon.