Computer Science/Discrete Mathematics Seminar I

In 1948, Shannon used a probabilistic argument to show 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 the involvement of various areas of discrete mathematics. In particular, the special case of the erasure channel was settled in 2015 by Kudekar et al., relying on Bourgain-Kalai's sharp threshold theorem for symmetric monotone properties. The case of error channels remained however unsettled, 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 conjecture. The proof circumvents the requirement of monotone properties to establish first a "weak" threshold property that relies solely on symmetries. From there on, the proof proceeds with a new boosting framework for coding, using sunflower structures and weight enumerator bounds from Sberlo-Shpilka to control the global error down to capacity. Joint work with Colin Sandon.